• <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;
            }
                    
            无码精品久久久久久人妻中字| 少妇久久久久久久久久| 精品999久久久久久中文字幕| 99久久久精品| 热综合一本伊人久久精品| 伊人久久大香线焦AV综合影院| 精品国产一区二区三区久久久狼 | 久久福利青草精品资源站| 久久99亚洲综合精品首页| 亚洲国产另类久久久精品黑人| 国产精品久久一区二区三区| 无码任你躁久久久久久| 久久国产精品99久久久久久老狼 | 日韩精品国产自在久久现线拍| 日本久久久久久久久久| 999久久久免费精品国产| 欧美日韩成人精品久久久免费看| 国产成人久久精品一区二区三区 | 99久久99久久精品国产片果冻| 久久久久国产精品人妻| 久久精品国产一区二区电影| 国内精品久久人妻互换| 伊人久久大香线蕉AV色婷婷色| 少妇被又大又粗又爽毛片久久黑人| 久久棈精品久久久久久噜噜| 久久午夜综合久久| 精品多毛少妇人妻AV免费久久| 成人国内精品久久久久一区| 久久亚洲美女精品国产精品| 亚洲午夜久久久影院| 国色天香久久久久久久小说| 综合久久一区二区三区| 亚洲一区精品伊人久久伊人 | 婷婷伊人久久大香线蕉AV | 99久久久国产精品免费无卡顿| 久久中文字幕人妻熟av女| 亚洲国产成人久久一区久久| 深夜久久AAAAA级毛片免费看| 国产精品无码久久久久| 久久久久九九精品影院| 合区精品久久久中文字幕一区 |