HDOJ 1232 畅通工程

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1232


经典的并查集应用~~~直接套模版就行了。
思路,找到小镇的father值等于自己的个数,减去1就是还要修的路。Orz

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 <iostream>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <assert.h>
#include <algorithm>
using namespace std;
 
#define MAX 1005
/* father[x]表示x的父节点 */
int father[MAX];
/* rank[x]表示x的秩 */
int rank[MAX]; 
 
/* 初始化集合 */
void Make_Set(int x)
{
        father[x] = x;
        rank[x] = 0;
} 
 
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
 
        if(x != father[x])
        {
                father[x] = Find_Set(father[x]);
        }
        return father[x];
} 
 
/* 按秩合并x,y所在的集合 */
void Union(int x, int y)
{
        x = Find_Set(x);
        y = Find_Set(y);
        if (x == y) return;
        if (rank[x] > rank[y])
        {
                father[y] = x;
        }
        else
        {
                if (rank[x] == rank[y])
                {
                        rank[y]++;
                }
                father[x] = y;
        }
} 
int N, M;
int main()
{
    int a, b;
    while(scanf("%d", &N) && N)
    {
        for(int i=1; i<=N; ++i)
            Make_Set(i);
        scanf("%d", &M);
        while(M--)
        {
            scanf("%d %d", &a, &b);
            Union(a, b);
        }
        int cnt = -1;
        for(int i=1; i<=N; ++i)
            if(father[i]==i)
                cnt++;
        printf("%d\n", cnt);
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注