首先，什么是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;
}