Problem Solving►UVa

UVa 796 - Critical Links

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

找 Bridge(Cut-edge)。

Solution

不用處理多重邊，參考：http://www.csie.ntnu.edu.tw/~u91029/Component.html#1。

Code

UVa 796
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#define N 100
using namespace std;

vector<int> adj_list[N];
int visited[N], low[N];
int n, step;
vector<pair<int, int>> bridges;

void DFS(int p, int u) //p -> u
{
    visited[u] = low[u] = ++step;

    for (int v : adj_list[u])
        if (v != p)
        {
            if (visited[v]) //back edge
            {
                //走一次 back edge 能到的
                low[u] = min(low[u], visited[v]);
                //不斷走 tree edge 與 back edge
                //low[u] = min(low[u], low[v]);
            }
            else //tree edge
            {
                DFS(u, v);
                low[u] = min(low[u], low[v]);
                if (visited[u] < low[v]) //u -> v 為bridge
                    bridges.emplace_back(min(u, v), max(u, v));
            }
        }
}
int main()
{
    //freopen("test.out", "w", stdout);
    while (scanf("%d", &n) != EOF)
    {
        int i, j, u, v;
        for (i = 0; i < n; ++i)
        {
            scanf("%d (%d)", &u, &j);
            while (j--)
            {
                scanf("%d", &v);
                adj_list[u].push_back(v);
            }
        }

        //find bridges (cut-edge)
        for (i = 0; i < n; ++i)
            if (!visited[i])
                DFS(i, i);

        sort(bridges.begin(), bridges.end(),
             [](const pair<int, int> &a, const pair<int, int> &b) -> bool {
                 return a.first < b.first || (a.first == b.first && a.second < b.second);
             });

        printf("%d critical links\n", (int)bridges.size());
        for (auto p : bridges)
            printf("%d - %d\n", p.first, p.second);
        putchar('\n');

        //init
        for (i = 0; i < n; ++i)
            adj_list[i].clear();
        memset(visited, 0, sizeof visited);
        memset(low, 0, sizeof low);
        bridges.clear();
        step = 0;
    }

    return 0;
}