樱桃网

#include<iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;

int n, m;
int p[N];

int find(int x)  //经典并查集
{
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T --){
        cin >> n >> m;
        int k = 0;

        for(int i = 1; i <= n; i ++) p[i] = i;  //并查集初始化

        for(int i = 0; i < m; i ++){
            int a, b;
            cin >> a >> b;
            if (find(a) != find(b)){
                p[find(a)] = find(b);
                k++;
            }
        }
        printf("Case #%d: %d\n",cnt ++, k + (n - k - 1) * 2);
    }
    return 0;
}