首先，什么是k連通圖?k連通圖就是指至少去掉k個點使之不連通的圖。此題依題意是要判斷此圖是否至少是3連通圖，直觀的想，枚舉兩個點，刪掉，看剩下的圖是否連通，但這樣做超時。可以優化為：枚舉刪去一個點，看是否還存在割點，如果存在割點，則不是3連通圖。代碼如下：
#include<iostream>
#include<vector>
using namespace std;
vector<int>list[501];
int low[501],dep[501];
int col[501];
int n,m;
bool flag=0;
int root;
int dfs(int u,int fa,int t)
{
col[u]=1;
dep[u]=low[u]=t;
int tol=0;
int i,v;
for(i=0;i<list[u].size();i++)
{
v=list[u][i];
if(col[v]==2)
continue;
if(col[v]==0)
{
dfs(v,u,t+1);
tol++;
low[u]=min(low[u],low[v]);
if(u==root&&tol>1||u!=root&&low[v]>=dep[u])
{
flag=1;//存在割點
}
}
else if(col[v]==1&&v!=fa)
{
low[u]=min(low[u],dep[v]);
}
}
return 0;
}
int main()
{
while(1)
{
scanf("%d%d",&n,&m);
if(n==0&&m==0)
break;
flag=0;
int i,j,a,b;
for(i=0;i<n;i++)
{
list[i].clear();
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
list[a].push_back(b);
list[b].push_back(a);
}
for(i=0;i<n;i++)//枚舉去掉一個點，判斷1，2連通性
{
memset(col,0,sizeof(col));
memset(dep,0,sizeof(dep));
memset(low,0,sizeof(low));
col[i]=2;
root=0;
if(i==0)
root=1;
dfs(root,-1,1);
for(j=0;j<n;j++)
{
if(col[j]==0)
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
system("pause");
return 0;
}