某种病毒袭击了某地区,该地区有N(1≤N≤50000)人,分别编号为0,1,...,N-1,现在0号已被确诊,所有0的直接朋友和间接朋友都要被隔离。例如:0与1是直接朋友,1与2是直接朋友,则0、2就是间接朋友,那么0、1、2都须被隔离。现在,已查明有M(1≤M≤10000)个直接朋友关系。如:0,2就表示0,2是直接朋友关系。 请你编程计算,有多少人要被隔离。 第一行包含两个正整数N(1≤N≤50000),M(1≤M≤100000),分别表示人数和接触关系数量; 在接下来的M行中,每行表示一次接触,; 每行包括两个整数U, V(0 <= U, V < N)表示一个直接朋友关系。 输出数据仅包含一个整数,为共需隔离的人数(包含0号在内)。
3
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,fa[500005],ans=1;
ll f(ll x){return x==fa[x]?x:fa[x]=f(fa[x]);}
int main(){
cin>>n>>m;
for(ll i=0;i<=n;i++)fa[i]=i;
for(ll i=1;i<=m;i++){
ll x,y;cin>>x>>y;
ll X=f(x),Y=f(y);
fa[X]=Y;
}
for(ll i=1;i<=n;i++){
if(f(i)==f(0))ans++;
}
cout<<ans<<endl;
}