• <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>

            POJ 1523 SPF 割點+分割連通塊的數(shù)量

            Description

            Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5, but communication between any other pairs of nodes would no longer be possible.

            Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.

            Input

            The input will contain the description of several networks. A network description will consist of pairs of integers, one pair per line, that identify connected nodes. Ordering of the pairs is irrelevant; 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty network description flags the end of the input. Blank lines in the input file should be ignored.

            Output

            For each network in the input, you will output its number in the file, followed by a list of any SPF nodes that exist.

            The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.

            Sample Input

            1 2
            5 4
            3 1
            3 2
            3 4
            3 5
            0
            1 2
            2 3
            3 4
            4 5
            5 1
            0
            1 2
            2 3
            3 4
            4 6
            6 3
            2 5
            5 1
            0
            0

            Sample Output

            Network #1
            SPF node 3 leaves 2 subnets
            Network #2
            No SPF nodes
            Network #3
            SPF node 2 leaves 2 subnets
            SPF node 3 leaves 2 subnets

            Source


                圖論,又是一道割點的題,并且還要求出圖中所有的割點分別能將圖分割成幾個不同的塊。可以將某個割點的訪問標(biāo)記設(shè)置為1,然后對圖進(jìn)行dfs,方法類似求圖中有幾個連通的區(qū)域。
            #include <iostream>
            #include 
            <vector>
            using namespace std;

            const int MAXN = 1010;
            bool flag,cut[MAXN],visit[MAXN];
            vector
            < vector<int> > adj;
            int mark[MAXN],deep[MAXN],ancestor[MAXN];

            void dfs(int u,int father,int depth){
                
            int i,v,son=0,len=adj[u].size();
                mark[u]
            =1,deep[u]=ancestor[u]=depth;
                
            for(i=0;i<len;i++){
                    v
            =adj[u][i];
                    
            if(v!=father && mark[v]==1)
                        ancestor[u]
            =min(ancestor[u],deep[v]);
                    
            if(mark[v]==0){
                        dfs(v,u,depth
            +1);
                        son
            =son+1;
                        ancestor[u]
            =min(ancestor[u],ancestor[v]);
                        
            if((father==-1 && son>1|| (father!=-1 && ancestor[v]>=deep[u]))
                            cut[u]
            =true;
                    }

                }

                mark[u]
            =2;
            }

            void partition(int u){
                visit[u]
            =true;
                
            int i,len=adj[u].size();
                
            for(i=0;i<len;i++)
                    
            if(!visit[adj[u][i]])
                        partition(adj[u][i]);
            }

            int main(){
                
            int i,j,x,y,n,cnt,ca=1;
                
            while(scanf("%d",&x),x){
                    scanf(
            "%d",&y);
                    adj.assign(MAXN,vector
            <int>());
                    n
            =max(x,y);
                    adj[x
            -1].push_back(y-1),adj[y-1].push_back(x-1);
                    
            while(scanf("%d",&x)){
                        
            if(x==0break;
                        scanf(
            "%d",&y);
                        n
            =max(x,y);
                        adj[x
            -1].push_back(y-1),adj[y-1].push_back(x-1);
                    }

                    memset(cut,
            false,sizeof(cut));
                    memset(mark,
            0,sizeof(mark));
                    
            for(i=0;i<n;i++)
                        
            if(mark[i]==0
                            dfs(
            0,-1,0);
                    printf(
            "Network #%d\n",ca++);
                    
            for(flag=false,i=0;i<n;i++)
                        
            if(cut[i]){
                            flag
            =true;
                            memset(visit,
            false,sizeof(visit));
                            
            for(visit[i]=true,cnt=j=0;j<n;j++)
                                
            if(!visit[j])
                                    partition(j),cnt
            ++;
                            printf(
            "  SPF node %d leaves %d subnets\n",i+1,cnt);
                        }

                    
            if(!flag)
                        printf(
            "  No SPF nodes\n");
                    printf(
            "\n");
                }

                
            return 0;
            }

            posted on 2009-05-28 19:18 極限定律 閱讀(1106) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久er国产精品免费观看2| 精品熟女少妇aⅴ免费久久| 久久噜噜久久久精品66| 青草影院天堂男人久久| 久久伊人精品青青草原高清| 国产精品久久网| 久久久91精品国产一区二区三区| 国产V综合V亚洲欧美久久| 99热成人精品热久久669| 51久久夜色精品国产| 久久亚洲高清综合| 合区精品久久久中文字幕一区| 中文字幕无码av激情不卡久久| 久久人做人爽一区二区三区| 囯产极品美女高潮无套久久久 | 99久久久精品免费观看国产| 亚洲精品白浆高清久久久久久| 国产精品久久久亚洲| 国产精品永久久久久久久久久| 四虎国产精品成人免费久久| 久久亚洲AV无码精品色午夜| 77777亚洲午夜久久多喷| 久久国产精品免费一区二区三区| 中文字幕久久亚洲一区| 精品国产一区二区三区久久| 国产精品熟女福利久久AV | 一本久久免费视频| 久久精品国产亚洲综合色| 中文字幕亚洲综合久久菠萝蜜| 无码AV波多野结衣久久| 中文精品久久久久国产网址| 久久精品国产亚洲AV香蕉| 久久精品国产99国产电影网 | 久久人人爽人人爽人人片AV不| 久久国产精品无码HDAV| 久久婷婷五月综合成人D啪| 久久香蕉国产线看观看精品yw| 日本欧美国产精品第一页久久| 精品久久久久久久无码| 精品无码久久久久国产动漫3d| 久久综合综合久久97色|