F题:https://ac.nowcoder.com/acm/contest/12794/F
题目大意:
该题就是给了n个样例,给出m对的节点连接情况,让你判断有多少个连接集团,以及有多少带环集团。

思路:
这题很显然运用到了并查集,通过并查集寻找集团个数,只需要寻找遍历节点,寻找有多少个父节点就是其本身的点,其次就是并查集找环,可以通过数组记录,在节点合并时进行记录,便可得到存在环的父节点。

解题代码:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
using namespace std;
const long long N = 1005;
const int maxn = 2e5 + 5;
const long long INF = 8e18;
typedef long long ll;
#define for0(i,n) for(int i = 0;i < n;i++)
#define for1(i,n) for(int i = 1;i <= n;i++)

int fa[N],vis[N],sig[N];

int Find(int x) 
{
    if(fa[x] == x)
        return x;
    else
        return fa[x] = Find(fa[x]);
}

void hebing(int x,int y){
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy){
        fa[fx] = fy;
        if(sig[fx]){
            sig[fy]=1;

        }

    }
    else{
        sig[fx]=1;
    }
}
int main()
{
    int n;
    cin >> n;

    for(int i=1;i <= n;i++){
        int s,c,num = 0;
        cin >> s >> c;
        for(int j=0;j <= s;j++){
            fa[j]=j;
            vis[j]=0;
            sig[j]=0;
        }
        int x,y;
        for(int j=0;j < c;j++){
            cin >> x >> y;
            vis[x]=1;
            vis[y]=1;
            hebing(x,y);
        }
        int tot=0;
        for(int j=1;j <= s;j++){
            if(j == fa[j] && vis[j]){
                tot++;
                if(sig[j] == 1){

                    num++;
                }
            }

        }
        printf("Night sky #%d: %d constellations, of which %d need to be fixed.\n\n",i,tot,num);

    }



    return 0;

}