PAT1013 并查集 DFS(查找联通分量的个数)

https://pintia.cn/problem-sets/994805342720868352/problems/994805500414115840

解题思路：大概就是求一个图的联通分量个数，求的时候不要把被占领的点加入集合中就可以了。

求联通分量大概就要先把联通的点放到一个集合中去，很容易想到并查集和DFS。很久没写过了，这里就两个都写一遍啦。

并查集：

#include<cstdio>

int road[1005][1005];

int N,M,K;
int parent[1005];

int second[1005];
//   并查集
void UFset()
{
    for(int i = 0;i < N;i++)
    {
         parent[i] = i;  // 每个人都是自己的根节点
         second[i] = -1;  // 此为PAT1013题目添加，使用时可以删除
    }

}
int Find(int root)
{
    int son = root;
    while(root != parent[root]) // 找到根节点
        root = parent[root];
    while(son != root)      // 路径压缩
    {
        int temp = parent[son];
        parent[son] = root;
        son = temp;
    }
    return root;
}

void Union(int R1,int R2)
{
    int r1 = Find(R1),r2 = Find(R2);    // 直接找到两个点的根
    if(r1 != r2) parent[r1] = r2; // 随便给一个根节点找个爹,合并两个集合
}

int main()
{
    scanf("%d%d%d",&N,&M,&K);

    for(int i = 1;i <= M;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        road[a][b] = 1;
        road[b][a] = 1;
    }
    while(K--)
    {
        int t;
        scanf("%d",&t);
        UFset();    // 每次都初始化一次
        for(int i = 1;i <= N;i++)
        {
            if(i == t) continue;
            for(int j = i+1;j <= N;j++)
            {
                if(j == t) continue;
                if(road[i][j]) Union(i,j);
            }
        }
        int ans = 0;
        for(int i = 1;i <= N;i++)
        {
            int r = Find(i);
            int flag = 0,x = ans;
            while(x--)
            {
                if(r == second[x])
                {
                    flag++;
                    break;
                }
            }
            if(!flag)
            {
                second[ans++] = r;
            }
        }
        printf("%d\n",ans-2);

    }

    return 0;
}

DFS

#include<cstdio>
#include<cstring>
int road[1005][1005];

int N,M,K;
int visit[1005];

int second[1005];

void DFS(int x)
{
    visit[x] = 1;
    for(int i = 1;i <= N;i++)
    {
        if(visit[i] != 1 && road[i][x] == 1)
            DFS(i);
    }
}


int main()
{
    scanf("%d%d%d",&N,&M,&K);
    memset(road,0,sizeof(road));
    for(int i = 1;i <= M;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        road[a][b] = 1;
        road[b][a] = 1;
    }
    while(K--)
    {
        int t;
        scanf("%d",&t);
        int ans = 0;
        memset(visit,0,sizeof(visit));
        visit[t] = 1;
        for(int i = 1;i <= N;i++)
        {
            if(visit[i] != 1)
            {
                DFS(i);
                ans++;
            }
        }
        printf("%d\n",ans-1);

    }

    return 0;
}