为了制作这道菜，他准备了N个樱桃，依次编号为1~N。
在他的甜点中，任意两个樱桃之间都存在着一条用糖构成的链条，将它们直接互相连接。
糖链呈红色或黑色，这取决于它们的含糖量。
每条黑色糖链含有一个单位的糖，每条红色糖链含有两个单位的糖。
在甜点完成之后，他发现甜点做的太甜了，而他的同学们都不喜欢吃含糖量过高的食物。
请你帮助他找出他应该去掉哪些糖链，使得这道菜的每对樱桃之间都能通过糖链直接或间接连接的同时，含糖量能够尽可能的最低？
输出这个含糖量的最小值。
输入格式
第一行包含整数T，表示共有T组测试数据。
每组数据第一行包含两个整数N和M，分别表示樱桃数量以及黑色糖链数量。
接下来M行，每行包含两个整数Ci和Di，表示编号为Ci和Di的两个樱桃之间存在一条黑色糖链。
注意：如果任意两个樱桃之间，没有被黑色糖链连接，那么说明它们之间由一条红色糖链连接。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为“Case #x: y”，其中x是组别编号（从1开始），y为含糖量的最小值。
数据范围
1≤T≤100,
M≤N∗(N−1)/2
1≤Ci,Di≤N,
Ci≠Di,
同一组数据内，所有{Ci， Di}对都互不相同。
1≤N≤105,
0≤M≤105
输入样例：
2
2 1
1 2
3 1
2 3
输出样例：
Case #1: 1
Case #2: 3
样例解释
在样例#1中，只有两个樱桃，它们之间由一个黑色糖链连接，去掉任何糖链都会使樱桃之间断连。
所以，含糖量的最小值为1。
在样例#2中，一种可行的方法是保留1和2之间的红色糖链以及2和3之间的黑色糖链。
所以，含糖量的最小值为3
方法一：连通块
二、打击犯罪
某个地区有 n 个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为 1∼n。
他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系。
所有可直接或间接联系的团伙被称为一个犯罪集团。犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为 n）。
现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过 n/2。
为达到最好的效果，他们将按顺序打击掉编号 1 到 k 的犯罪团伙，请编程求出 k 的最小值。
注意： 数据保证至少存在一个犯罪集团的危险程度超过 n/2。
输入格式
第一行一个正整数 n。
接下来的 n 行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第 i 行存在正整数 k，表示 i,k 两个团伙可以直接联系。
输出格式
一个正整数，为 k 的最小值。
数据范围
1≤n≤1000
输入样例：
7
2 2 5
3 1 3 4
2 2 4
2 2 3
3 1 6 7
2 5 7
2 5 6
输出样例：
1
方法一：邻接表+并查集
将单个团伙的危险程度理解成团伙人数，然后一个团伙有多个邻邦，团伙和其邻邦的总人数即为危险程度
题目要求顺序打击，这一点可以配合反向思维来做，先打击第 n-i 到 第 n 个团伙：
- 如果此时这些团伙的总危险程度 \(>\cfrac{n}{2}\)，则前面的 1~i 个集团一定不超过 \(\cfrac{n}{2}\)；
- 反之我还可继续缩减 i
注：顺序打击意味着第 i 个团伙后序的团伙的编号 x 必须大于 i，而如果 x≤i 即使他们有联系，也不能打击 x
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int fa[N], sz[N];
vector<int> g[N];
int find(int u) {
return fa[u]==u ? u : fa[u]=find(fa[u]);
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin>>n;
for (int i=1; i<=n; i++) {
int m, x; cin>>m, fa[i]=i, sz[i]=1;
for (int j=1; j<=m; j++)
cin>>x, g[i].push_back(x);
}
for (int i=n; i>0; i--)
for (int x : g[i]) if (x>i) {
int fi=find(i), fx=find(x);
if (fi!=fx) {
fa[fi]=fx;
sz[fx]+=sz[fi];
if (sz[fx]>(n>>1)) {
return cout << i, 0;
}
}
}
return 0;
}