Pagini recente » Borderou de evaluare (job #1470516) | Borderou de evaluare (job #1444662) | Borderou de evaluare (job #1244364) | Borderou de evaluare (job #292625) | Cod sursa (job #1800392)
#include <fstream>
#define NMAX 100000
using namespace std;
int n,m,t[NMAX+100],nivele[NMAX+100];
ifstream f("dfs.in");
ofstream g("dfs.out");
int gasesc(int c){
if(c==t[c])
return c;
t[c]=gasesc(t[c]);
return t[c];
}
void unesc(int a, int b){
if(nivele[a]<nivele[b])
t[a]=b;
else
if(nivele[a]>nivele[b])
t[b]=a;
else{
t[a]=b;
nivele[b]++;
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=n;i++){
t[i]=i;
nivele[i]=1;
}
for(int i=1;i<=m;i++){
int x,y,a,b;
f>>x>>y;
if((a=gasesc(x))!=(b=gasesc(y)))
unesc(a,b);
}
int nr=0;
for(int i=1;i<=n;i++)
if(t[i]==i)
nr++;
g<<nr;
return 0;
}