|
|
Posted on 2010-08-08 19:46 Uriel 阅读(453) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 图论
赤裸裸的求割点数的题目，上模板~~ 关于求割点的方法，黑书上讲得比较详细了
 //Problem: 1144 User: Uriel
//Memory: 228K Time: 16MS
//Language: C++ Result: Accepted
//Cut Vertex
//2010.08.06
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 110
int n;
int ancestor[N];
int mark[N];
int deep[N];
int cnt[N];
int adj[N][N];
  int DFS(int i,int father,int dth,int b[][N],int cut[]) {
 int j,k,sons=0,count=0;
mark[i]=1;
deep[i]=ancestor[i]=dth;
  for(k=b[i][0];k>=1;k--){
j=b[i][k];
if(j!=father && mark[j]==1)ancestor[i]=min(ancestor[i],deep[j]);
if(mark[j]==0){
count+=DFS(j,i,dth+1,b,cut);
sons++;
ancestor[i]=min(ancestor[i],ancestor[j]);
if((father==-1&&sons>1)||(father!=-1&&ancestor[j]>=deep[i]))cut[i]=1;
//if(ancestor[j]>deep[i]) brige[i][j]=1;
 }
}
mark[i]=2;
return count+cut[i];
 }
int cutpoints(int a[][N],int n,int cut[]){
int i,j,b[N][N],count=0;
for(i=0;i<n;i++)cut[i]=b[i][0]=0;
memset(mark,0,sizeof(mark));
for(i=0;i<n;i++)for(j=0;j<n;j++)if(a[i][j])b[i][++b[i][0]]=j;
for(i=0;i<n;i++)if(mark[i]==0)count+=DFS(0,-1,0,b,cut);
return count;
}
int main(){
int x,y;
char c;
while(1){
scanf("%d",&n);
if(!n)return 0;
memset(adj,0,sizeof(adj));
while(1){
scanf("%d",&x);
if(x==0)break;
x--;
while(1){
scanf("%d",&y);
y--;
adj[x][y]=1;adj[y][x]=1;
c=getchar();
if(c=='\n')break;
}
}
printf("%d\n",cutpoints(adj,n,cnt));
}
return 0;
}
|