其實就是判斷是否為三連通圖
三連通圖指的是去掉3個點就不連通的圖，但是并沒有直接求三連通的算法。著名的Tarjan算法可以求解連通和割點，再枚舉刪除一個點就能達到三連通的目的。
先看用例2，是由用例1去掉一條邊而變成非三連通圖的：
至少造成了2和3非三連通：
我們來思考如何推導出2和3非三連通，假設從上圖中刪除了節點0，通過Tarjan算法，我們可以發現節點1是割點：
?
那么只需刪除從3到割點和從3到我們枚舉刪除的節點0的兩條邊，就可以將3和2分割開來：
才刪除了兩條邊2和3就不連通了，這個圖顯然不是三連通圖。
?
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxn = 20010; int cnt,flag,times,del,root; int head[maxn],low[maxn],dfn[maxn]; struct no {int v,next; }Eg[2*maxn]; void init( ) {cnt=0;memset(head,-1,sizeof(head)); } void add(int form,int to) {Eg[cnt].v=to;Eg[cnt].next=head[form];head[form]=cnt++; } void dfs(int u,int fa) {if(flag)return ;int tot=0;low[u] = dfn[u] = ++times;for(int i=head[u] ; i!=-1 ; i=Eg[i].next){int v=Eg[i].v;if(v==fa||v==del)continue;if(!dfn[v]){tot++;dfs(v,u);low[u]=min(low[u],low[v]);//判斷割點if((u==root&&tot>1)||(u!=root&&low[v]>=dfn[u]))flag=1;}elselow[u]=min(low[u],dfn[v]);} } int main( ) {int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;init();for(int i=0 ; i<m ; i++){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);}flag=0;for(int i=0 ; i<n ; i++){del = i ; times = 0;memset(dfn,0,sizeof(dfn));root = 0;if(del==0)root=1;dfn[del] = 1;dfs(root,-1);for(int j=0 ; j<n ; j++){if(!dfn[j]){flag=1;break;}}if(flag)break;}if(flag)puts("NO");elseputs("YES");}return 0;}
?
)
)
