Problem Solving►UVa

UVa 11504 - Dominos

Contents

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

Problem

題目網址
中文網址

Solution

沒做過 Tarjan’s Algorithm，起初打算用 DFS 直接做，但從不一樣的點開始推都會影響，應該不太可行了…

找出 SCC，再利用這些點收縮後的 component (形成 DAG)，找各個的 入邊(in-edge) (不知道有沒有 in-edge 這個講法…)。
只要沒有入邊，就代表一定要從這裡開始推。而有入邊的可以透過其他 component 連過去。

作法參考：http://www.csie.ntnu.edu.tw/~u91029/Component.html#4

我想最關鍵的地方就是如果有 back edge，則還在 stack 中 back edge 所能到的最高祖先 及 它的子孫們 可以形成 SCC。
其餘詳細部分就請自行查閱了。

把樹畫出可以幫助理解，可以用裡面的圖：https://youtu.be/ju9Yk7OOEb8

附上個 udebug 的測資：(畫出來~)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
IN:
1
12 13
1 2
2 3
3 4
4 1
6 3
6 7
7 8
8 9
9 6
12 2
12 10
10 11
11 12

OUT:
3

Code

UVa 11504
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cstring>
//#include <stack>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define N 100001

struct edge
{
    int v, next;
} E[N];
int adj[N]; //adjacent list
int low[N], visited[N];
int step;

bool in_stack[N];
//std::stack<int> S;
int Stack[N], top;
int contract[N], component; //收縮的點, 收縮後的點數
bool in_deg[N];             //有無入邊(in-edge)
//int have_in;

inline int read()
{
    int n = 0;
    char c;
    while ((c = getchar()) >= '0' && c <= '9')
        n = n * 10 + c - '0';
    return n;
}
void DFS(int u)
{
    visited[u] = low[u] = ++step;
    //S.push(u);
    Stack[top++] = u;
    in_stack[u] = true;

    for (int i = adj[u]; i != -1; i = E[i].next)
    {
        int v = E[i].v;
        if (!visited[v]) //tree edge
            DFS(v);

        if (in_stack[v]) //已經走過但還未成 SCC 的點
            low[u] = MIN(low[u], low[v]);
        else //連到一個 SCC，該 SCC 就有了入邊
            in_deg[contract[v]] = true;

        /*else if(!in_deg[contract[v]])
        {
            in_deg[contract[v]] = true;
            ++have_in;
        }*/
    }

    //形成 SCC，將整串(也可能一點)從 DFS tree 中移除
    if (visited[u] == low[u]) //u 是 SCC 中最早拜訪的點
    {
        ++component;
        while (true)
        {
            /*int v = S.top();
            S.pop();*/
            int v = Stack[--top];
            in_stack[v] = false;
            contract[v] = component; //記下該收縮點

            if (v == u)
                break;
        }
    }
}
int main()
{
    //freopen("test.out","w",stdout);
    int n, m, Case;
    scanf("%d ", &Case);
    while (Case--)
    {
        memset(adj, -1, sizeof adj);
        //scanf("%d%d", &n, &m);
        n = read();
        m = read();
        int u, v, idx = 0;
        for (int i = 0; i < m; ++i)
        {
            //scanf("%d%d", &u, &v);
            u = read();
            v = read();
            E[idx] = (edge){v, adj[u]}; //u -> v
            adj[u] = idx++;
        }

        for (int i = 1; i <= n; ++i)
            if (!visited[i])
                DFS(i);

        //(已在DFS中計算)
        //用每個邊計算各收縮後點的入邊數(超過 1 就不用再算)
        /*for (u = 1; u <= n; ++u)
            for (int i = adj[u]; i != -1; i = E[i].next)
            {
                //u -> v
                int v = E[i].v;

                if (contract[u] != contract[v] && !in_deg[contract[v]])
                    in_deg[contract[v]] = true;
            }*/

        int ans = 0;
        for (int i = 1; i <= component; ++i)
            if (!in_deg[i])
                ++ans;

        printf("%d\n", ans);

        //printf("%d\n", component - have_in);

        //init
        top = component = step = 0;
        memset(visited, 0, sizeof visited);
        memset(in_deg, false, N);
        memset(in_stack, false, N);
        //have_in = 0;
        //memset(low, 0, sizeof low);
        //memset(contract,0,sizeof contract);
    }

    return 0;
}