题意:给一个无向图,判断这个图是否存在奇环和偶环。
解法:网上有一种只用dfs就能做的解法,但是我不太理解。
这里用的是比较复杂的。首先奇环很简单可以用二分图染色判断。问题是偶环怎么判断?这里我们想,一旦有两个环共享了一些点,那么这两个环一定能组成一个偶环。
那么我们考虑tarjan找出所有桥删去,那么对于一个边双联通分量,这个边双只要有多于一个环就必定存在偶环。即当且仅当这个边双为一个奇环的情况下才不存在偶环,其他情况都会有偶环。
所以一旦这个边双不是单环,就必定存在偶环。
那么怎么判断这个是不是一单个环呢?点数=边数的时候就是一个单环。
细节详见代码:
#pragma comment(linker,"/STACK:102400000,102400000") #include<bits/stdc++.h> using namespace std; const int N=3e5+10; int n,m,ver,edge,odd,even,col[N]; bool bridge[N]; int cnt=1,head[N<<1],nxt[N<<1],to[N<<1]; void add_edge(int x,int y) { nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt; } int num,low[N],dfn[N]; void tarjan(int x,int in) { dfn[x]=low[x]=++num; for (int i=head[x];i;i=nxt[i]) { int y=to[i]; if (!dfn[y]) { tarjan(y,i); low[x]=min(low[x],low[y]); if (low[y]>dfn[x]) bridge[i]=bridge[i^1]=1; } else if (i!=(in^1)) low[x]=min(low[x],dfn[y]); } } void dfs(int x,int fa) { col[x]=3-col[fa]; ver++; for (int i=head[x];i;i=nxt[i]) { if (bridge[i]) continue; int y=to[i]; edge++; if (y==fa) continue; if (!col[y]) dfs(y,x); else if (col[x]==col[y]) odd=1; else even=1; //染色过程判断奇偶环 } } int main() { int T; cin>>T; while (T--) { cin>>n>>m; cnt=1; for (int i=1;i<=n;i++) head[i]=0; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x); } num=0; for (int i=1;i<=n;i++) dfn[i]=low[i]=0; for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,0); //找桥 odd=even=0; for (int i=1;i<=n;i++) col[i]=0; col[0]=1; for (int i=1;i<=n;i++) if (!col[i]) { ver=0; edge=0; dfs(i,0); if (ver>1 && edge/2!=ver) even=1; //点数和边数不等,存在偶环 } printf("%s\n",odd?"YES":"NO"); printf("%s\n",even?"YES":"NO"); for (int i=0;i<=cnt;i++) bridge[i]=0; } return 0; }