• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(462) 評論(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;
            }
                    
            国产精品99久久久久久www| 久久中文字幕人妻熟av女| 久久夜色精品国产亚洲| 久久99精品久久久久久野外| 亚洲午夜久久久| 99久久99久久| 99久久国产亚洲综合精品| 国内精品久久久久| 性高朝久久久久久久久久| 精品久久人妻av中文字幕| 久久精品国产99久久丝袜| 久久精品无码专区免费青青| 欧美日韩成人精品久久久免费看| 国产精品久久毛片完整版| 免费无码国产欧美久久18| 国产香蕉97碰碰久久人人| 久久亚洲国产成人精品性色| 久久夜色精品国产亚洲av| 色综合久久精品中文字幕首页| 麻豆精品久久久久久久99蜜桃| 久久精品二区| 精品久久久久久久中文字幕| 精品综合久久久久久97超人| 色婷婷综合久久久久中文 | 久久久久久曰本AV免费免费| 久久久精品免费国产四虎| 久久久久国产精品熟女影院| 97精品伊人久久久大香线蕉| 色综合久久天天综线观看| 久久精品国产亚洲Aⅴ蜜臀色欲| 久久电影网2021| 777久久精品一区二区三区无码| A狠狠久久蜜臀婷色中文网| 亚洲成色www久久网站夜月| 久久人做人爽一区二区三区| 亚洲午夜福利精品久久 | 久久亚洲AV成人无码国产| 亚洲色大成网站www久久九 | 国产V亚洲V天堂无码久久久| 久久这里只有精品18| 精品无码久久久久久午夜|