牛客多校(2020第八场)I

Apollo is playing an interesting computer game. There are N rounds in the game.
At each round, the computer will give Apollo two integers (

aia_iai​ and bib_ibi​), and Apollo can do exactly one of the following three actions.

Apollo can do nothing.
If integer $aia_iai has not been selected in all previous rounds, Apollo can select integer aia_iai.$
If integer $bib_ibi has not been selected in all previous rounds, Apollo can select integer bib_ibi.$

输入描述:

The first line is an integer  $10^51≤N≤105), indicating the number of rounds in this game.Then N lines follow. The i-th line contains two integers aia_iai​ and bib_ibi​ (1≤ai≤1091 le a_i le 10^91≤ai​≤109, 1≤bi≤1091 le b_i le 10^91≤bi​≤109), indicating that two integers of the i-th round.$

输出描述:

For each test case, output one line containing

示例1

输入

输出

Case #1: 4
Case #2: 4

题意：

给了俩个数组a, b
第i步可从ai和bi种选择一个数
求最后选择的数的个数，不同的数要多

题解：

　首先要想到可以用并查集做题，然后将ai, bi看成俩个点，[ai, bi]看成一条边，所以题目会给出 n 条边，然后根据并查集的合成，会形成一个或多个连通块。

　连通块有俩种形式

有环：n个点，n条边，如果选数，每条边可以选择一个点，则最多可以选择 n 个数
无环：n个点，n-1条边，如果选数，则只能选择n-1个数

　最后，因为ai, bi的数据有点大，所以需要对数据进行离散化，可以选择使用map数组或者unordered_map(当然unordered_map效率会更高一些)。

 1 /* 
 2 并查集，离散化
 3 合并的集合n个顶点有环，则可选择n个，无环则只能选择n-1个
 4  */
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<cstring>
 8 #include<unordered_map>
 9 
10 using namespace std;
11 
12 typedef long long ll;
13 const int N = 1e5+5;
14 
15 int par[2 * N];//并查集数组,记录每个结点的父节点
16 bool circle[2 * N]; //记录有没有环
17 unordered_map<int, int> mp; //离散化,第一个是原来的值，第二个是离散化后的值
18 
19 inline int read() {
20     int x = 0, f = 1;
21     char ch = getchar();
22     while(ch<'0'||ch>'9'){
23         if(ch=='-')
24             f=-1;
25         ch=getchar();
26     }
27     while(ch>='0'&&ch<='9'){
28         x = x * 10 + ch - '0';
29         ch = getchar();
30     }
31     return x * f;
32 }
33 
34 int find(int x) {
35     return par[x] == x ? x : par[x] = find(par[x]); //如果自己是自己的父节点则返回自己，否则寻找父节点的父节点，并更新
36 }
37 
38 void merge(int x, int y) {
39     int par_x = find(x), par_y = find(y); //寻找x, y的父节点
40     if (par_x != par_y) { //父节点不同，则合并
41         par[par_x] = par_y; //将x的父节点的父节点设置为y
42         circle[par_y] |= circle[par_x]; //若x的父节点有环，则y的父节点也该变为有环(需位的或操作)
43     }
44     else {
45         circle[par_x] = true; //若父节点相同，则其有环
46     }
47 }
48 
49 void init() {
50     mp.clear();
51     for (int i = 0; i < 2 * N; i++) {
52         par[i] = i;
53         circle[i] = false;
54     }
55 }
56 
57 int main() {
58     int t;
59     t = read();
60     for (int k = 1; k <= t; k++) {
61         init();
62         int n = read();
63 
64         int cnt = 0; //用于离散化
65         for (int i = 0; i < n; i++) {
66             int a, b;
67             a = read();
68             b = read();
69             //离散化
70             if (!mp[a]) mp[a] = ++cnt;
71             if (!mp[b]) mp[b] = ++cnt;
72             merge(mp[a], mp[b]);
73         }
74 
75         int ans = cnt;
76         
77         for (int i = 1; i <= cnt; i++) {
78             if (!circle[i] && par[i] == i)  ans--; //对于每个并查集，如果无环则需减1
79         }
80         printf ("Case #%d: %d
", k, ans);
81     }
82 }