Problem Solving►UVa

UVa 615 - Is It A Tree

Contents

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

Problem

中文網址

Solution

邊建邊，邊記下每個指向此節點的邊數。先利用題目中的三條規則來判斷，再遍歷一次圖形看是否都連通(我是用BFS)即可。
記得處理沒有任何點的狀況。

Code

UVa 615
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
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#define M 100
using namespace std;

vector<int> adjList[M];
bool BFS(int n, int root);
int main()
{
    int u, v, ref[M] = {}, Case = 1;
    map<int, int> Map;

    while (scanf("%d%d", &u, &v) && u >= 0)
    {
        int i, idx = 0;
        while (u)
        {
            if (!Map.count(u))
                Map[u] = ++idx;
            if (!Map.count(v))
                Map[v] = ++idx;

            adjList[Map[u]].push_back(Map[v]);
            ref[Map[v]]++;

            scanf("%d%d", &u, &v);
        }

        int root = -1;
        bool ans = true;
        for (i = 1; i <= idx; i++)
        {
            if (!ref[i])//不只一個 root
            {
                if (root != -1)
                {
                    ans = false;
                    break;
                }

                root = i;
            }
            else if (ref[i] > 1)//有節點被兩個以上的點指著
            {
                ans = false;
                break;
            }
        }

        //沒有任何節點時，仍為一棵樹
        if (idx)
        {
            if (root == -1)//沒有root
                ans = false;
            else if (ans)//BFS 判斷是否連通
                ans = BFS(idx, root);
        }

        printf("Case %d is%sa tree.\n", Case++, ans ? " " : " not ");

        for (i = 1; i <= idx; i++)
        {
            ref[i] = 0;
            adjList[i].clear();
        }

        Map.clear();
    }


    return 0;
}
bool BFS(int n, int root)
{
    bool isVisit[M] = {};
    queue<int> Q;
    Q.push(root);
    isVisit[root] = true;

    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();

        for (int v : adjList[u])
        {
            if (!isVisit[v])
                isVisit[v] = true;
            else return false;

            Q.push(v);
        }
    }

    for (int i = 1; i <= n; i++)
        if (!isVisit[i])
            return false;

    return true;
}