社区讨论
求大佬给看看,只有50分,第9个点还re了
P1330封锁阳光大学参与者 6已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mi6m3k11
- 此快照首次捕获于
- 2025/11/20 07:06 4 个月前
- 此快照最后确认于
- 2025/11/20 07:06 4 个月前
CPP
#include<iostream>
#include<algorithm>
using namespace std;
struct line
{
int next;
int to;
}edge[1000000];
int tot;
int g[100000];
int n, m;
int ans[3];
void add(int a, int b)
{
tot++;
edge[tot].to = b;
edge[tot].next = g[a];
g[a] = tot;
}
bool flag = true;
int color[100000];
void dfs(int a, int c)
{
color[a] = c;
ans[c + 1]++;
int temp = g[a];
while (temp != 0)
{
int x = edge[temp].to;
if (color[x] == c) { flag = false;return; }
if (color[x] == 0)
{
dfs(x, -c);
}
temp = edge[temp].next;
}
return ;
}
int main()
{
int ans1 = 0;
cin >> n >> m;
for (int i = 0;i < m;i++)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1;i <= tot;i++)
{
if (color[i] == 0)
{
ans[0] = 0;
ans[2] = 0;
dfs(i, 1);
ans1 += min(ans[0], ans[2]);
}
}
if (!flag)cout << "Impossible";
else
{
cout << ans1;
}
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...