• <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>
            posts - 18,  comments - 5,  trackbacks - 0

            一、題目描述

            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


            二、分析
                  用DFS解決問題,詳細算法:割點與橋
            三、代碼

             1#include<iostream>
             2#include<list>
             3using namespace std;
             4int t;
             5int v1, v2;
             6list<int> g[1001];
             7bool flag;
             8int root;
             9int counter;
            10bool spf[1001];
            11int low[1001], lab[1001];
            12bool visit[1001];
            13void dfs(int u, int fa)
            14{
            15    low[u] = lab[u] = counter++;
            16    list<int>::iterator it;
            17    int counter = 0;
            18    for(it = g[u].begin(); it != g[u].end(); it++)
            19    {
            20        int v = *it;
            21        if(!lab[v])
            22        {
            23            counter++;
            24            dfs(v, u);
            25            low[u] = min(low[u], low[v]);
            26            if((u==root && counter>=2|| (u!=root && low[v]>=lab[u]))
            27                spf[u] = flag = true;
            28        }

            29        else if(v != fa)
            30            low[u] = min(low[u], lab[v]);
            31    }

            32}

            33void find(int u)
            34{
            35    visit[u] = true;
            36    list<int>::iterator it;
            37    for(it = g[u].begin(); it != g[u].end(); it++)
            38        if(!visit[*it])
            39            find(*it);
            40}

            41int main()
            42{
            43    t = 1;
            44    while(1)
            45    {
            46        scanf("%d"&v1);
            47        if(v1 == 0break;
            48        for(int i=1; i<=1000; i++)
            49            g[i].clear();
            50        memset(spf, 0sizeof spf);
            51        memset(low, 0sizeof low);
            52        memset(lab, 0sizeof lab);
            53        while(v1 != 0)
            54        {
            55            scanf("%d"&v2);
            56            g[v1].push_back(v2);
            57            g[v2].push_back(v1);
            58            root = v1;
            59            scanf("%d"&v1);
            60        }

            61        counter = 1;
            62        flag = false;
            63        dfs(root, -1);
            64        printf("Network #%d\n", t++);
            65        if(flag)
            66        {
            67            for(int i=1; i<=1000; i++)
            68            {
            69                if(!spf[i]) continue;
            70                int cnt = 0;
            71                memset(visit, 0sizeof visit);
            72                visit[i] = true;
            73                list<int>::iterator it;
            74                for(it = g[i].begin(); it != g[i].end(); it++)
            75                    if(!visit[*it])
            76                    {
            77                        cnt++;
            78                        find(*it);
            79                    }

            80                    printf("  SPF node %d leaves %d subnets\n", i, cnt);
            81            }

            82        }

            83        else
            84            printf("  No SPF nodes\n");
            85        printf("\n");
            86    }

            87}
            posted on 2009-07-04 16:12 Icyflame 閱讀(1182) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            久久人人添人人爽添人人片牛牛| 色婷婷综合久久久久中文字幕| 亚洲人成网亚洲欧洲无码久久| 欧美伊人久久大香线蕉综合 | 久久久久久国产a免费观看黄色大片 | 久久se精品一区精品二区国产| 久久精品国产欧美日韩| 久久99精品久久久大学生| 国产人久久人人人人爽| 热RE99久久精品国产66热| 久久国产精品无码HDAV| 欧美国产成人久久精品| 久久久久99精品成人片欧美| 久久乐国产精品亚洲综合 | 国产午夜福利精品久久| 一本久久a久久精品vr综合| 久久亚洲av无码精品浪潮| 久久777国产线看观看精品| 久久久久亚洲AV成人网人人网站| 国产午夜精品理论片久久| AV色综合久久天堂AV色综合在| 免费一级做a爰片久久毛片潮| 曰曰摸天天摸人人看久久久| 囯产极品美女高潮无套久久久 | 久久精品国产福利国产琪琪| 丁香五月网久久综合| 日韩精品久久久肉伦网站 | 国内精品伊人久久久久影院对白 | 精品久久久久久国产三级| 97久久国产亚洲精品超碰热| 亚洲va中文字幕无码久久不卡| 久久天天躁狠狠躁夜夜2020 | 精品国产青草久久久久福利| 久久国产免费观看精品| 色8久久人人97超碰香蕉987| 久久99热这里只有精品国产| 久久这里的只有是精品23| 亚洲人成无码网站久久99热国产| 久久久久亚洲?V成人无码| 精品久久久久久久中文字幕| 久久精品国产清自在天天线|