解释：（转自洛谷题解）
首先，肯定要明确一点，那就是这个图是不一定联通的。于是，我们就可以将整张图切分成许多分开的连同子图来处理。然而最重要的事情是：如何处理一个连通图？
乍看下去，似乎无从下手，因为方案好像有很多种，根本就枚举不完。但是，关键要注意到题目中重要的两个条件，我们把它抽象成这两个要素：
又因为我们要处理的是一个连通图。所以，对于这一个图的点的选法，可以考虑到相邻的点染成不同的颜色。
所以，我们只需要找到每一个子连通图，对它进行黑白染色，然后取两种染色中的最小值，然后最后汇总，就可以了。
另外，要判断impossible，只需要加一个used数组，记录已经遍历了哪些点。如果重复遍历一个点，且与上一次的颜色不同，则必然是impossible的。、
my code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define rep(i, a, b) for (int i = a; i <= b; ++i) 5 6 const int N = 1e5 + 7; 7 8 int n, m, vis[N], cnt[3], ans; 9 10 bool used[N]; 11 12 vector<int> e[N]; 13 14 void dfs(int u, int col) { 15 if (!used[u]) { 16 used[u] = 1; 17 vis[u] = col; 18 cnt[col]++; 19 for (auto v : e[u]) { 20 dfs(v, 3 - col); 21 } 22 } 23 else if (col != vis[u]) { 24 puts("Impossible"); 25 exit(0); 26 } 27 } 28 29 int main() { 30 scanf("%d%d", &n, &m); 31 32 rep(i, 1, m) { 33 int u, v; 34 scanf("%d%d", &u, &v); 35 e[u].push_back(v); 36 e[v].push_back(u); 37 } 38 39 rep(i, 1, n) if (!used[i]) { 40 cnt[1] = cnt[2] = 0; 41 dfs(i, 1); 42 ans += min(cnt[1], cnt[2]); 43 } 44 45 printf("%d\n", ans); 46 47 return 0; 48 }
原文：https://www.cnblogs.com/Fo0o0ol/p/10100002.html