解題區/解題區 - UVa

UVa 12363 - Hedge Mazes

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一無向圖，問任兩點是否存在唯一的路徑到達。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
4 2 3
1 2
2 3
1 4
1 3
1 2
0 0 0

Sample Output

1
2
3
4
5
6
7
8
Y
N
N
-
N
Y
Y
-

Solution

唯一路徑，保證 x - y 之間走過的只會有橋 (由很多橋構成)，將所有橋找到，並且將橋兩端利用并查集合併 (構成大橋)

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[131072];
int visited[131072], depth[131072];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    int back = 0x3f3f3f3f;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        if(!visited[v]) {
            int b = findBridge(v, u, dep+1);
            if(b > dep) {
                bridge.push_back(make_pair(u, v));
            }
            back = min(back, b);
        } else {
            back = min(back, depth[v]);
        }
    }
    return back;
}
int rank[131072], parent[131072];
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)	return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], parent[y] = x;
    else
        rank[y] += rank[x], parent[x] = y;
}
int main() {
    int n, m, q, x, y;
    while(scanf("%d %d %d", &n, &m, &q) == 3 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        bridge.clear();
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                findBridge(i, -1, 0);
            }
        }
        
        for(int i = 0; i < n; i++)
            rank[i] = 1, parent[i] = i;
        for(int i = 0; i < bridge.size(); i++)
            joint(bridge[i].first, bridge[i].second);
        for(int i = 0; i < q; i++) {
            scanf("%d %d", &x ,&y);
            x--, y--;
            puts(findp(x) == findp(y) ? "Y" : "N");
        }
        puts("-");
    }
    return 0;
}