加边的时候就用并查集维护一下
by aiyougege @ 2018-06-16 11:16:31
检查连通图时，并查集应该是最快的吧
by Siyuan @ 2018-06-16 11:17:59
每次`add_edge(u,v)`时`fa[get_fa()u]=get_fa(v)`就行了
by Siyuan @ 2018-06-16 11:18:39
@[siyuan](/space/show?uid=49725) 可这不是生成并查集的做法吗？跟检查图是否连通有什么直接关系？并查集形成好几组的话整个图不也不连通么
by 少帅_zjm @ 2018-06-16 11:23:06
```c++
#include<cstdio>
#define N 200005
using namespace std;
struct Edge{
int v,nxt;
}e[N];
int head[N],tot;
void AddEdge(int u,int v){
e[++tot]=(Edge){v,head[u]};head[u]=tot;
e[++tot]=(Edge){u,head[v]};head[v]=tot;
}
int f[N];
int find(int s){
return f[s]==s?s:f[s]=find(f[s]);
}
int main(){
int n,m,a,b,siz=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)f[i]=i;
for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
if(find(a)!=find(b))++siz;
f[find(a)]=find(b);
}
if(siz>n-2)
printf("true");
else printf("false");
}
```
by aiyougege @ 2018-06-16 11:27:55
@[少帅_zjm](/space/show?uid=46694) 大概可以这么做
by aiyougege @ 2018-06-16 11:28:13
@[aiyougege](/space/show?uid=39067) 把那个size>n-2改成size==n-1行吗？
by 少帅_zjm @ 2018-06-16 11:36:26
n-1不是说形成一棵树嘛
by 少帅_zjm @ 2018-06-16 11:37:19
可以吧
by aiyougege @ 2018-06-16 11:40:46