Problem Solving►UVa

UVa 11518 - Dominos 2

Contents

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

Problem

題目網址
中文網址

Solution

直接把能推的都先放進列隊裡，接著做 BFS 就行了。

Code

UVa 11518
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
#include <cstdio>
#include <cstring>
#include <queue>
#define N 10001

struct node
{
    int v, next;
};
inline int read()
{
    int n = 0;
    char ch;
    while ((ch = getchar()) >= '0' && ch <= '9')
        n = n * 10 + ch - '0';

    return n;
}
int main()
{
    //freopen("test.out", "w", stdout);
    
    int adj[N];//adjacent list
    node edge[N];
    bool visited[N];

    int T;
    scanf("%d ", &T);
    while (T--)
    {
        int n = read(), m = read(), l = read();
        //scanf("%d%d%d ", &n, &m, &l);

        memset(visited, false, sizeof visited);
        memset(adj, -1, sizeof adj);
        int idx = 0;

        int u, v;
        for (int i = 0; i < m; ++i)
        {
            //scanf("%d%d", &u, &v);
            u = read();
            v = read();
            edge[idx] = (node){v, adj[u]};
            adj[u] = idx++;
        }

        std::queue<int> Q;
        for (int i = 0; i < l; ++i)
        {
            //scanf("%d", &u);
            u = read();
            if (!visited[u]) //防止推一樣的
            {
                visited[u] = true;
                Q.push(u);
            }
        }

        int ans = 0;
        while (!Q.empty())
        {
            ++ans;
            int now = Q.front();
            Q.pop();

            for (int i = adj[now]; i != -1; i = edge[i].next)
            {
                int v = edge[i].v;
                if (!visited[v])
                {
                    visited[v] = true;
                    Q.push(v);
                }
            }
        }

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

    return 0;
}