Problem Solving►UVa

UVa 11709 - Trust groups

Contents

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

Problem

題目網址
中文網址

Solution

再練習一次 Tarjan’ Algo. 。

Code

UVa 11709
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
#include <cstdio>
#include <cstring>
#include <string>
#include <unordered_map>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define N 1000
#define T 999000
using namespace std;

struct edge
{
    int v, next;
} E[T];
unordered_map<string, int> M;
int adj[N];
int visited[N], low[N], step;
int component;
bool in_stack[N];
int Stack[N], top;

void DFS(int u)
{
    visited[u] = low[u] = ++step;
    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])
            DFS(v);

        if (in_stack[v])
            low[u] = MIN(low[u], low[v]);
    }

    if (visited[u] == low[u])
    {
        ++component;
        while (true)
        {
            int v = Stack[--top];
            in_stack[v] = false;
            if (v == u)
                return;
        }
    }
}
int main()
{
    int P, t;
    char str[30];
    while (scanf("%d%d", &P, &t) && (P || t))
    {
        getchar();
        for (int i = 0; i < P; ++i)
        {
            fgets(str, 30, stdin);
            M[string(str)] = i;
        }

        memset(adj, -1, sizeof adj);
        int idx = 0;
        for (int i = 0; i < t; ++i)
        {
            int u, v;
            fgets(str, 30, stdin);
            u = M[string(str)];
            fgets(str, 30, stdin);
            v = M[string(str)];

            E[idx] = (edge){v, adj[u]};
            adj[u] = idx++;
        }

        for (int i = 0; i < P; ++i)
            if (!visited[i])
                DFS(i);

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

        //init
        top = component = step = 0;
        memset(visited, 0, sizeof visited);
        memset(low, 0, sizeof low);
    }

    return 0;
}