按照某老师说的保密要求，题目不放上来，要原题的请在评论区附上证明自己是南海区学生的证明
那这题作为填坑第一弹是因为突然想起那时候眼睁睁看着wyl写了好几个优化版本而我连题目都看不懂，虽然现在看这题目很简单（笑cry）。
说一下做法。自己的做法是在线做法（在线：读一组处理一组，相对应的是离线，全部读入后再处理）。每读入一条边，这条边连接的俩结点有5种情况：
- 同根，两点在树上
- 同根，两点在有环图上
- 不同根，两点各自在一个树上
- 不同根，一个点在树上，一个点在有环图上
- 不同根，两点各自在一个有环图上
以数据1-2, 1-3, 2-3, 3-4, 5-6, 6-7, 7-8, 8-9, 3-8为例
插入1-2和2-3都是情况3，显然tree--。而插入2-3时是情况1，因为123已经是一棵树了，连接2-3后变成了环，所以除了tree--还要标记123变成了有环图。
插入3-4就是情况4，tree--后把4和123合并。
其后5-6-7-8-9这四条边使得56789成了一棵树，当连接3-8时又遇到了情况4。当1234与56789合并时，1234会成为56789的子结点，此时56789的根结点要标记为有环图。和第二幅图对比，情况4时要把合并后的根结点标记为有环图。再联想一下或运算，0|0=0,0|1=1,1|0=1，用0表示树，1表示有环图，那么情况3和4就可以用或运算一起处理！
很明显2和5的情况都是不用管的，因为在有环图形成时就已经tree--了。
最后的代码特别短，美滋滋~
#include <cstdio>
#include <algorithm>
const int MAXN = 1e5 + 1;
int f[MAXN], sz[MAXN];
bool cycle[MAXN];
int uf_find(int p) {
if (f[p] == p)
return p;
return f[p] = uf_find(f[p]);
}
void uf_union(int p, int q) {
if (sz[p] < sz[q])
swap(p, q);
f[q] = f[p];
sz[p] += sz[q];
cycle[p] |= cycle[q];
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
int n, m, u, v, i, tree, ru, rv;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
f[i] = i, sz[i] = 1;
tree = n;
for (i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
ru = uf_find(u);
rv = uf_find(v);
if (ru == rv && !cycle[ru]) { //1
tree--;
cycle[ru] = true;
}
else if (!(cycle[ru] & cycle[rv])) { //3,4
tree--;
uf_union(ru, rv);
}
}
printf("%d
", tree);
return 0;
}
情况2在程序中的处理比较巧妙。对于情况2, 由于根被标记为有环图，所以到了elseif处，此时u与v的根结点相同，都标记为有环图，所以又跳出了if。情况5不说了，很清楚。
标程错了三个点已无力吐槽……另外贴上姚焜茗大佬的不知什么原理但更快的代码：
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int n, m, ans, father[maxn];
bool boo[maxn];
int find(int x) {
int y = x;
while (father[y] > 0)
y = father[y];
while (x != y) {
int tmp = father[x];
father[x] = y;
x = tmp;
}
return x;
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
father[i] = -1;
for (int i = 1; i <= m; i++){
int x, y;
scanf("%d%d", &x, &y);
int x_father = find(x),
y_father = find(y);
if (x_father == y_father) {
boo[x_father] = true;
continue;
}
if (x_father < y_father) {
if (boo[y_father]) {
boo[x_father] = true;
boo[y_father] = false;
}
father[x_father] += father[y_father];
father[y_father] = x_father;
} else {
if (boo[x_father]) {
boo[y_father] = true;
boo[x_father] = false;
}
father[y_father] += father[x_father];
father[x_father] = y_father;
}
}
for (int i = 1; i <= n; i++)
if (father[i] < 0 && !boo[i])
ans++;
printf("%d
",ans);
return 0;
}