Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1144 Network---求无向图割点数

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;
}
        

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理