青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

POJ 1523 SPF 割點+分割連通塊的數量

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


    圖論,又是一道割點的題,并且還要求出圖中所有的割點分別能將圖分割成幾個不同的塊。可以將某個割點的訪問標記設置為1,然后對圖進行dfs,方法類似求圖中有幾個連通的區域。
#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 極限定律 閱讀(1107) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美电影在线观看完整版| 久久久成人网| 国产精品成人免费精品自在线观看| 亚洲日本理论电影| 亚洲经典自拍| 欧美日韩中文精品| 久久成人亚洲| 久久久综合精品| 一区二区精品在线观看| 正在播放亚洲一区| 黄色国产精品| 亚洲国产日韩美| 国产精品美女999| 久久三级福利| 欧美搞黄网站| 羞羞色国产精品| 久久午夜影视| 亚洲专区一区| 另类人畜视频在线| 亚洲一区二区动漫| 久久久久久久久久久一区| 99成人在线| 先锋影音久久| 在线亚洲欧美专区二区| 欧美在线亚洲| 亚洲视频日本| 久久综合久色欧美综合狠狠| 亚洲一区二区三区高清| 久久综合给合久久狠狠狠97色69| 一区二区欧美日韩视频| 久久av一区二区三区亚洲| 夜夜嗨av色综合久久久综合网| 香蕉av777xxx色综合一区| 亚洲免费精彩视频| 久久久久这里只有精品| 亚洲欧美日韩在线| 久久九九久精品国产免费直播| 99re6这里只有精品| 久久国产视频网| 香蕉成人伊视频在线观看 | 麻豆久久婷婷| 国产精品婷婷午夜在线观看| 欧美高清hd18日本| 国产尤物精品| 亚洲自拍偷拍视频| 亚洲一区二区精品在线| 欧美高清视频www夜色资源网| 久久久久欧美精品| 国产精品羞羞答答xxdd| 99天天综合性| 亚洲无线视频| 欧美日韩成人| 亚洲精品免费观看| 亚洲伦理在线观看| 麻豆av福利av久久av| 久久综合色天天久久综合图片| 国产精品亚洲综合| 亚洲一区二区三区高清不卡| 亚洲影院一区| 国产精品你懂的| 亚洲一区免费在线观看| 性色av一区二区三区红粉影视| 欧美日韩精品免费看| 亚洲国产mv| 亚洲国产精彩中文乱码av在线播放| 小处雏高清一区二区三区| 午夜精品久久久久久久蜜桃app| 欧美系列电影免费观看| 一区二区三区精品视频在线观看| 国产精品99久久久久久久久| 欧美精品一卡| 在线视频欧美日韩精品| 性感少妇一区| 韩国v欧美v日本v亚洲v| 久久午夜影视| 91久久线看在观草草青青| 一区二区三区黄色| 国产精品免费电影| 羞羞视频在线观看欧美| 久久亚洲一区二区三区四区| 在线不卡a资源高清| 欧美顶级艳妇交换群宴| 欧美午夜在线一二页| 一本色道久久综合一区| 欧美一区二区三区四区在线观看| 国产综合视频在线观看| 久久综合久久综合久久| 99re66热这里只有精品3直播| 亚洲一区中文| 一区二区三区自拍| 欧美日韩国产成人在线| 亚洲欧美成人网| 欧美成人免费一级人片100| 亚洲视频国产视频| 国内一区二区三区| 欧美裸体一区二区三区| 亚洲自拍电影| 亚洲福利视频三区| 欧美亚洲系列| 亚洲品质自拍| 国产精品久久久久久久第一福利| 久久国产精品久久久久久久久久 | 久久一区二区精品| 亚洲免费精彩视频| 激情久久久久久| 欧美日韩视频在线观看一区二区三区| 亚洲一区欧美一区| 亚洲国产一区在线| 久久久777| 亚洲一区二区三区三| 亚洲高清av在线| 国产伦精品一区二区三区四区免费 | 亚洲一区精彩视频| 亚洲成人资源网| 国产精品一区二区在线观看网站| 久久免费视频一区| 亚洲综合导航| 亚洲日本欧美| 欧美高清免费| 久久先锋资源| 欧美中文字幕久久| 亚洲一区二区欧美日韩| 亚洲国产精品久久91精品| 国产偷国产偷精品高清尤物| 国产精品啊v在线| 欧美精品久久久久久久久老牛影院| 久久成人一区二区| 午夜久久美女| 亚洲欧美视频| 亚洲尤物精选| 亚洲日韩第九十九页| 国产亚洲欧美一区二区| 国产精品爽黄69| 国产精品国产a| 欧美午夜片在线观看| 欧美日韩亚洲一区二区三区在线观看 | 欧美大胆人体视频| 蜜桃久久av一区| 免费视频久久| 免播放器亚洲一区| 欧美成人免费在线| 欧美国产日韩一区| 欧美人与禽猛交乱配视频| 欧美精品v日韩精品v国产精品| 欧美11—12娇小xxxx| 欧美国产欧美亚洲国产日韩mv天天看完整| 久久久久久9999| 麻豆免费精品视频| 欧美国产日韩精品免费观看| 欧美黄网免费在线观看| 欧美日本一区| 国产精品视频网址| 韩国女主播一区二区三区| 精品电影在线观看| 亚洲精品裸体| 日韩视频在线播放| 亚洲午夜小视频| 欧美在线播放一区| 麻豆精品网站| 亚洲人屁股眼子交8| 宅男在线国产精品| 欧美一区二区大片| 欧美xxxx在线观看| 欧美午夜视频一区二区| 国产网站欧美日韩免费精品在线观看| 黄色小说综合网站| 日韩视频免费在线| 小黄鸭精品aⅴ导航网站入口| 久久久久网站| 亚洲欧洲在线视频| 亚洲图中文字幕| 久久香蕉国产线看观看av| 欧美日韩国产一区二区三区地区| 国产精品美女久久福利网站| 经典三级久久| 在线中文字幕不卡| 久久综合久久久久88| 亚洲毛片网站| 久久精品中文| 国产精品老牛| 亚洲精品中文字幕有码专区| 欧美一区二区女人| 亚洲区在线播放| 欧美亚洲一区| 国产精品v片在线观看不卡| 在线观看视频日韩| 午夜精品免费在线| 亚洲国产精品久久久久秋霞不卡| 亚洲午夜久久久| 欧美激情精品久久久六区热门| 国产欧美日本一区二区三区| 日韩一级黄色av| 久久亚洲春色中文字幕| 亚洲香蕉成视频在线观看| 欧美va天堂| 激情成人综合网| 欧美主播一区二区三区| 一区二区三区日韩精品| 欧美成人亚洲成人| 亚洲国产另类久久精品|