英雄联盟阵营

coding>C++
1.3k 词

题目描述

符文之地——瓦罗兰，作为最大的一块魔法大陆，它居于符文之地心脏中心，是符文之地面积最大的大陆。所有谋求符文之地霸权的势力，都将焦点放在了瓦罗兰。
近200年来的战争和纷争导致魔法滥用，军队用法术和符文武装自己，英雄们打造出大部分魔法物品率领部队厮杀。他们拥有近乎无限的原始魔法力量使用，从未考虑过无止境的滥用魔法会给这片大陆的环境带来怎么样的灾难。最后两次符文之战影响了瓦罗兰的地质环境。地震和魔法风暴让整个瓦罗兰为之颤抖，对人们来说这份恐惧远超过战争的恐怖。人们终于意识到世界已经承受不起符文之战的破坏。
为了回应世界上不断恶化的政治和经济危机，瓦罗兰的大法师们达成共识，冲突以可控和系统化的方式来处理。他们成立了一个叫英雄联盟的组织。
但联盟的纷争并没有消失,以德玛西亚和诺克萨斯等阵营的英雄们继续为他们的信念而战。 

输入

第一行有两个整数$n,m$。
n$(0<n<100)$表示有n个英雄；m$(0<m<100)$表示接下来有m行数据。
接下来m行，每行都有两个整数a,b。表示a，b英雄在同一个阵营。在默认情况下，任意两个英雄不在同一阵营。

输出

输出n个英雄的阵营的个数。

样例输入

1
2
3
4
5  3
1  2
2  3
4  5

样例输出

1
2

题解

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
#include <map>
#include <iostream>
#include <iterator>
using namespace std;
#define endl '\n'
const int maxn = 100;
int F[maxn];
void init(int n) {
    for (int i = 1; i <= n; i++)F[i] = i;
}
bool is_root(int x) {
    return F[x] == x;
}
int find(int x) {
    if (is_root(x))return x;
    return F[x] = find(F[x]);
}
bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)return false;
    F[fx] = fy;
    return true;
}
int count(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)if (F[i] == i)++cnt;
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    int x, y;
    while (cin >> n >> m) {
        init(n);
        while (m--) {
            cin >> x >> y;
            merge(x, y);
        }
        cout << count(n) << endl;
    }
    return 0;
}