这道题竟然是橙色的:
因为可以用并查集来做,当然您用dfs也可以,不过应该要加优化。
一开始就把读入的合并起来,最后逐个查找就好啦。。。
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,m,ans,q[MAXN];
int fa[MAXN];
int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
x=find(x);
y=find(y);
fa[y]=x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
if(find(a)!=find(b)) merge(a,b);
}
for(int i=;i<=n;i++)
if(!q[find(i)]){
q[find(i)]=;
ans++;
}
printf("%d",ans);
return ;
}