洛谷P2097 资料分发1 题解

题目传送门

这道题竟然是橙色的：

因为可以用并查集来做，当然您用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=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(find(a)!=find(b)) merge(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!q[find(i)]){
               q[find(i)]=1;
            ans++;
        }
    printf("%d",ans);
    return 0;
}