Posted on 2010-08-08 20:54
Uriel 阅读(292)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
图论
判一个无向图是不是至少3-连通
方法是枚举点，去掉一个点之后判余下的图中是否存在割点，如果都存在，则是至少3-连通，否则就不是
//Problem: 3713 User: Uriel
//Memory: 2164K Time: 3922MS
//Language: C++ Result: Accepted
//enumration & cut vertex
//2010.08.07
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 510
int n,m,cnt,root;
int ancestor[N];
int mark[N];
int deep[N];
int b[N][N];
int adj[N][N];
bool flag;
int DFS(int u,int fa,int t)
{
mark[u]=1;
deep[u]=ancestor[u]=t;
int cnt=0;
int i,v;
for(i=b[u][0];i>=1;i--){
v=b[u][i];
if(mark[v]==2)continue;
if(mark[v]==0){
DFS(v,u,t+1);
cnt++;
ancestor[u]=min(ancestor[u],ancestor[v]);
if(u==root && cnt>1 || u!=root && ancestor[v]>=deep[u])flag=1;
}
else if(mark[v]==1 && v!=fa){
ancestor[u]=min(ancestor[u],deep[v]);
}
}
return 0;
}
int main(){
int x,y,i,j;
while(scanf("%d %d",&n,&m),n|m){
memset(adj,0,sizeof(adj));
for(i=0;i<n;i++)b[i][0]=0;
for(i=0;i<m;i++){
scanf("%d %d",&x,&y);
adj[x][y]=adj[y][x]=1;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(adj[i][j])b[i][++b[i][0]]=j;
}
}
flag=false;
for(i=0;i<n;i++){
memset(mark,0,sizeof(mark));
memset(deep,0,sizeof(deep));
memset(ancestor,0,sizeof(ancestor));
mark[i]=2;
if(i==0)root=1;
else
root=0;
DFS(root,-1,1);
for(j=0;j<n;j++){
if(mark[j]==0){
flag=true;
break;
}
}
if(flag)break;
}
if(flag)puts("NO");
else
puts("YES");
}
return 0;
}