前言:
这是一个很不错的思维题!
思路:
这个题就是要让我们来证明一幅图必须有奇数环,才能使得全图被遍历(假如按2步走的话).
首先我们对于一棵树来说,我们知道假如我们不走到叶子节点再还回肯定是没有意义的,但是其实我们走到叶子节点再还回也是没有意义的.
比方说我们现在有两条链,奇数链和偶数链.
奇数链:1->2,2->3.我们会发现走到叶子节点是没有意义的,无法改变他来时的点的位子.
偶数链:1->2,2->3,3->4.同样的,这里也是没有意义的,1->3,3->3.还是没改变.
好!接下来是偶数环.
偶数环:1->2,2->3,3->4,4->1.无论我们怎么走,来时哪个点,回来时也是哪个点.
但是,奇数环就不一样了~
它直接改变了奇偶性质.综上,我们就证明了.
代码:
用染色法判断奇数环即可.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; vector<int>g[N]; int deg[N],root=0; int color[N]; int odd_circle=1; void dfs(int u,int col) { if(color[u]!=-1) { if(color[u]!=col) odd_circle=0; return; }color[u]=col; for(int x:g[u]) dfs(x,1-col); } int main() { memset(color,-1,sizeof color); int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v;scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); }int ans=-1; for(int i=1;i<=n;i++) { if(color[i]==-1) { dfs(i,1);ans++; } }ans+=odd_circle; printf("%d\n",ans); return 0; }