并查集（合并集合，连通块的点的数量）

836. 合并集合

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

一共有 n

个数，编号是 1∼n

，最开始每个数各自在一个集合中。

现在要进行 m

个操作，操作共有两种：

1. M a b，将编号为 a

和 b

• 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
• Q a b，询问编号为 a
• 和 b
  1. 的两个数是否在同一个集合中；

  输入格式

  第一行输入整数 n

  和 m

  。

  接下来 m

  行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

  输出格式

  对于每个询问指令 Q a b，都要输出一个结果，如果 a

  和 b

  在同一集合内，则输出 Yes，否则输出 No。

  每个结果占一行。

  数据范围

  1≤n,m≤105

  输入样例：

  4 5
  M 1 2
  M 3 4
  Q 1 2
  Q 1 3
  Q 3 4
  

  输出样例：

  Yes
  No
  Yes
  

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 1e5+10;
int fath[maxn];
 
int find(int u)
{
    if(fath[u]<0)
        return u;
    else
        fath[u]=find(fath[u]);
}
 
int main()
{
    int n,m;
    cin >> n >> m;
    
    fill(fath,fath+maxn,-1);
    while (m -- )
    {
        char op;
        int u,v;
        cin >> op >> u >> v;
        
        int fau=find(u),fav=find(v);
        
        if(op == 'M')
        {
            if(fau!=fav)
                fath[fau]=fav;
        }
        else 
        {
            if(fau==fav)
                puts("Yes");
            else 
                puts("No");
        }
        
    }
    
    return 0;
}

837. 连通块中点的数量

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个包含 n

个点（编号为 1∼n

）的无向图，初始时图中没有边。

现在要进行 m

个操作，操作共有三种：

1. C a b，在点 a

和点 b 之间连一条边，a 和 b

• 可能相等；
• Q1 a b，询问点 a
• 和点 b 是否在同一个连通块中，a 和 b
• 可能相等；
• Q2 a，询问点 a

1. 所在连通块中点的数量；

输入格式

第一行输入整数 n

和 m

。

接下来 m

行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 a

和 b

在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a

所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 1e5+10;
int fath[maxn];
 
int find(int u)
{
    if(fath[u]<0)
        return u;
    else
        fath[u]=find(fath[u]);
}
 
int main()
{
    int n,m;
    cin >> n >> m;
    
    fill(fath,fath+maxn,-1);
    
    while (m -- )
    {
        string op;
        int u,v;
        cin >> op;
        
        if(op == "C")
        {
            cin >> u >> v;
            int fau=find(u),fav=find(v);
            if(fau!=fav)
            {
                fath[fav]+=fath[fau];
                fath[fau]=fav;
            }
        }
        else if(op == "Q1")
        {
            cin >> u >> v;
            int fau=find(u),fav=find(v);
            if(fau==fav)
                puts("Yes");
            else 
                puts("No");
        }
        else 
        {
            cin >> u;
            cout << -fath[find(u)] << endl;
        }    
        
    }
    
    return 0;
}