|
Posted on 2010-08-08 19:46 Uriel 阅读(445) 评论(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; }
|