sdnu1351.the Number of Department（并查集模板）

Description

    Company A has N employees, this company has lots of departments around the country. The employees who belong to different departments do not know each other, but if two employees are working in the same department they will know each other directly or indirectly (For example, 1 and 2 know each other directly,2 and 3 know each other directly, so 1 and 3 know each other indirectly, and they belong to the same department).
    These N employees are numbered from 1 to N.
    Now, giving you M informations about these N employees (two employees' number, who knows each other directly).
    If any people did not appear in the list of the M informations, these people belong to different departments.
    Now, you should calculate how many departments this company has.

Input

    The 1st line, N, ( 1<=N<=10000 ) the number of the employees belong to the company.
    The 2ed line, M, ( 1<=M<=100000 ) the number of the informations about these N employees.
    The next M lines, each line has two numbers, i and j, said that employee i and j knows each other directly.

Output

    The maximum number of the departments that belong to company A.

Sample Input

11 
9
1 2
4 5
3 4
1 3
5 6
7 10
5 10
6 10
8 9

Sample Output

3

模板题。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int pre[N];
int Find(int x)
{
    if(x==pre[x])
        return x;
    int fx=Find(pre[x]);
    return pre[x]=fx;
}

void join(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)
        pre[fx]=fy;
}

int main()
{
    int m,n,t;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%d",&m);
        memset(pre,0,sizeof(pre));
        for(int i=0;i<=n;i++)
            pre[i]=i;
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            join(a,b);
        }
        set<int>st;
        for(int i=1;i<=n;i++)
        {
            int tmp=Find(i);
            st.insert(tmp);
        }
        int tmp=st.size();
        cout<<tmp<<'\n';
    }
    return 0;
}