解題區/解題區 - UVa

UVa 879 - Circuit Nets

contents

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

Problem

給定一組電路的連接，請問有多少個電網個數。

Sample Input

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

Sample Output

1
3

Solution

單純查找連通子圖的個數，使用并查集完成。

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
#include <stdio.h>
#include <sstream>
using namespace std;
int parent[65536], weight[65536];
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 (weight[x] > weight[y])
        parent[y] = x, weight[x] += weight[y];
    else
        parent[x] = y, weight[y] += weight[x];
    return 1;
}
int main() {
    int testcase, n;
    char line[1024];
    scanf("%d", &testcase);
    while (getchar() != '\n');
    while (getchar() != '\n');
    while (testcase--) {
        scanf("%d", &n);
        while (getchar() != '\n');
        for (int i = 0; i < n; i++)
            parent[i] = i, weight[i] = 1;
        int ret = n, x, y;
        while (gets(line) && line[0] != '\0') {
            stringstream sin(line);
            while (sin >> x >> y) {
                x--, y--;
                ret -= joint(x, y);
            }
        }
        printf("%d\n", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
1
14
 1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10 
*/