68 lines
1.9 KiB
C++
68 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
//dfs代码简短一些，注意第29行。
|
||
const int N = 1e4 + 10; //题目中说结点数最大10^4=1e4
|
||
const int M = 1e5 * 2 + 10; //边数上限，因为是无向图，所以记录两次，就是1e5*2
|
||
|
||
//链式前向星
|
||
struct Edge {
|
||
int to, next;
|
||
} e[M];
|
||
int head[N], idx;
|
||
|
||
void add(int u, int v) {
|
||
e[++idx].to = v;
|
||
e[idx].next = head[u];
|
||
head[u] = idx;
|
||
}
|
||
|
||
int n, m, ans, ans1, ans2;
|
||
int color[N]; //上色结果
|
||
|
||
/**
|
||
* 功能：对二分图进行上色
|
||
* @param u 要上色的结点
|
||
* @param c 上一个过来结点的颜色
|
||
*/
|
||
void dfs(int u, int c) {
|
||
//上一个结点颜色是1，那么u就是2
|
||
if (c == 1) color[u] = 2, ans2++;
|
||
//上一个结点颜色是2，那么u就是1
|
||
else if (c == 2) color[u] = 1, ans1++;
|
||
//遍历每个出边
|
||
for (int i = head[u]; i; i = e[i].next) {
|
||
int v = e[i].to;
|
||
//如果已上色
|
||
if (color[v] > 0) {
|
||
//颜色与上一个结点的颜色一样，那么就是冲突
|
||
if (color[v] == color[u]) {
|
||
printf("Impossible");
|
||
exit(0);
|
||
}
|
||
}//未上色，则进行上色即可
|
||
else dfs(v, color[u]);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
cin >> n >> m;
|
||
int x, y;
|
||
for (int i = 1; i <= m; ++i) {
|
||
cin >> x >> y;
|
||
add(x, y), add(y, x);//无向图，双向创建
|
||
}
|
||
//寻找每个结点，如果没有染过颜色，就深度优先开始染色
|
||
for (int i = 1; i <= n; ++i)
|
||
if (!color[i]) {
|
||
//每一轮用之前清空为零
|
||
ans1 = ans2 = 0;
|
||
dfs(i, 1);//假设第一个结点是颜色1
|
||
//两种颜色哪个少哪个是答案
|
||
ans += min(ans1, ans2);
|
||
}
|
||
//如果有解，那么输出
|
||
printf("%d", ans);
|
||
return 0;
|
||
} |