本文主要是介绍ZJU1311 Network - 无向图的割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
给出一个无向图，求图中割点的个数。（若去掉顶点i及其邻边，导致剩下的图不连通，则i是割点）
分析：
求割点有很成熟的DFS算法，照书写了一个，整理成模板备用。
- /*
- ZJU1311 Network
- */
- #include <stdio.h>
- #include <memory.h>
- #define clr(a) memset(a,0,sizeof(a))
- #define MIN(a,b) ((a)>(b)?(b):(a))
- #define N 105
- int n;
- int a[N][N];
- int cut[N];
- char* Next(char str[],char *sp){
- while(*sp&&*sp!=' ') sp++;
- while(*sp&&*sp==' ') sp++;
- return sp;
- }
- /**************************************/
- int ancestor[N];
- int mark[N];
- int deep[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];
- }
- /*
- 求割点
- 参数：a[][]邻接矩阵，非0表示连通。n顶点个数。
- 返回：割点数量，cut[i]==1表示i是割点。
- 说明：DFS算法，先将邻接矩阵转换为邻接表，可以处理图本身不连通的情况。复杂度O(E)
- 可稍作修改求图的桥。
- */
- 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 i,j,k;
- char str[N*10],*sp;
- while(scanf("%d",&n)!=EOF && n){
- //init
- clr(a);
- //input
- while(scanf("%d",&i),i){
- gets(str);
- for(sp=Next(str,str);sscanf(sp,"%d",&j)!=EOF;sp=Next(str,sp)){
- a[i-1][j-1]=a[j-1][i-1]=1;
- }
- }
- //work
- printf("%d/n",cutpoints(a,n,cut));
- }
- return 0;
- }
这篇关于ZJU1311 Network - 无向图的割点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
