题目描述

你的朋友最近完成了烹饪课的学习，现在他想通过做出一个美味的甜点来在他的同学面前展现他的学习成果。

他想出了一种叫樱桃网的甜点。

为了制作这道菜，他准备了N个樱桃，依次编号为1~N。

在他的甜点中，任意两个樱桃之间都存在着一条用糖构成的链条，将它们直接互相连接。

糖链呈红色或黑色，这取决于它们的含糖量。

每条黑色糖链含有一个单位的糖，每条红色糖链含有两个单位的糖。

在甜点完成之后，他发现甜点做的太甜了，而他的同学们都不喜欢吃含糖量过高的食物。

他现在遇到了困惑，特地向你求助。

请你帮助他找出他应该去掉哪些糖链，使得这道菜的每对樱桃之间都能通过糖链直接或间接连接的同时，含糖量能够尽可能的最低？

输出这个含糖量的最小值。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含两个整数N和M，分别表示樱桃数量以及黑色糖链数量。

接下来M行，每行包含两个整数$C_i$和$D_i$，表示编号为$C_i$和$D_i$的两个樱桃之间存在一条黑色糖链。

注意：如果任意两个樱桃之间，没有被黑色糖链连接，那么说明它们之间由一条红色糖链连接。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case #x: y”，其中x是组别编号（从1开始），y为含糖量的最小值。

数据范围

$ 1≤T≤100 $,
$M≤N∗(N−1)/2$
$1≤C_i,D_i≤N$,
$ C_i≠D_i $,
同一组数据内，所有${C_i， D_i}$对都互不相同。
$1≤N≤10^5$,
$0≤M≤10^5$

样例

输入样例：

2
2 1
1 2
3 1
2 3

输出样例：

Case #1: 1
Case #2: 3

算法1

(并查集) $O(n)$

• 采用策略：要求出最少的含糖量数，那么就要找到最小生成树。
• 此处为了节省空间采用并查集的方法求，即先求出黑色边的个数，设为k，那么剩下的点则即为(n - k - 1),这些点则含糖值为2，所以最后值为k + 2 *(n - k - 1)。

时间复杂度

一层循环 $O(n)$

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;

const int N = 1E5 + 10;

int n, m;
int f[N];

int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[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 ++) f[i] = i;

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