solution
我们从1号点开始染色,标记为0的点表示可以从1号点走偶数步到达,标记为1的点表示可以从1号点走奇数步到达。最后就是想要所有点都可以标记为0。如果存在一个奇环,那么这个环上的点既可以标记为1,也可以标记为0,所以所有与这个奇环相连的点都可以标记为0和1。
所以我们只要保证最终连接成一个包含奇环的连通块就可以了,如果存在至少一个连通块里本来就有一个奇环,那么只要让其他连通块向其连边即可,答案就是(S表示连通块个数)。如果不存在一个连通块里有奇环,那么就要自己连出一个奇环,显然连出一个奇环只需要添加1条边,所以答案就是。
判断一个连通块内是不是存在奇环可以用二分图染色。如果无法进行二分图染色就表明该连通块内存在奇环。
code
/* * @Author: wxyww * @Date: 2020-05-20 13:54:52 * @Last Modified time: 2020-05-20 14:40:48 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } struct node { int v,nxt; }e[N << 1]; int head[N],ejs; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } int vis[N],ANS = 1; void dfs(int u,int fa) { vis[u] = vis[fa] + 1; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v;if(v == fa) continue; if(vis[v]) { if(!((vis[v] - vis[u]) & 1)) ANS = 0; continue; } dfs(v,u); } return; } int main() { int n = read(),m = read(); for(int i = 1;i <= m;++i) { int u = read(),v = read(); add(u,v);add(v,u); } int ans = 0; for(int i = 1;i <= n;++i) { if(vis[i]) continue; ans++; dfs(i,0); } cout<<ans - 1 + ANS; return 0; }