poj_1523.txt

poj 1523的代码和方法说明,个人原创

#include<iostream>using namespace std;int parts[1001],rankk[1001],visited[1001],gra[1001][1001],out[1001],roots,por[1001],set[1001];int dfs(int root,int rank,int father)//利用深度优先生成树的性质,一次dfs求出所有割点,顺便在确定是割点的同时计算出分割数{                     //root表示当前节点,rank表示深度级别,其中根节点为rank为1,father表示root的直接父节点 visited[root]=1; rankk[root]=rank; int i; int pp=0;//记录分割数 int ans=rank,j,ff=rank;//ff表示在遍历这个节点和它的子孙时可以回溯到的级别最小的祖先 for(i=1;i<=out[root];i++)//遍历所以直接连接的点,但父节点除外;   if(gra[root][i]!=father)   {    if(visited[gra[root][i]])    {        if(ff>rankk[gra[root][i]])                   ff=rankk[gra[root][i]];                }         else      {       j=dfs(gra[root][i],rank+1,root);       if(j==-1)//如果不可以回溯到祖先,那么这个点是割点,并把它的分割数加1;        pp++;       else if(j<ff)       {    ff=j;        ans=1;       }      }   }   if(root==roots)   {       parts[root]=pp;//记录分割数;     por[root]=(pp!=1);   }   else   {    if(pp)    { por[root]=1;    parts[root]=pp+1;    }    else//如果任何子树都可以回溯到祖先,那么它不是割点     por[root]=0;   }    if(ff==rank||ff==rankk[father])     return -1;//返回-1表示不可以回溯到祖先;    else     return ff;//返回可以回溯到的最远祖先}  
 
   
 
int main(){ int i,j,k,cas=0,n;    while(scanf("%d",&i)&&i)    {  cas++;       n=0;cc:  scanf("%d",&j);       out[i]++;         out[j]++;      set[i]=set[j]=1;     gra[i][out[i]]=j;     gra[j][out[j]]=i;      scanf("%d",&i);   if(i==0)   {    roots=1; 
    dfs(1,1,-1);//从根节点1开始遍历一次,计算出割点和他们对应的的分割数    printf("Network #%d\n",cas);           int flag=0;       for(i=1;i<=1000;i++)        if(set[i]&&por[i])     {      printf("  SPF node %d leaves %d subnets\n",i,parts[i]);      flag=1;     }     if(flag==0)                     cout<<"  No SPF nodes\n";     cout<<endl;
    memset(out,0,sizeof(out));    memset(set,0,sizeof(set));    memset(visited,0,sizeof(visited));     }   else    goto cc;    }    return 0;}