Pagini recente » Cod sursa (job #518736) | Cod sursa (job #2277726) | Cod sursa (job #2510696) | Cod sursa (job #203111) | Cod sursa (job #633116)
Cod sursa(job #633116)
#include <fstream>
#define Nmax 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,h[Nmax],tata[Nmax],nrc;
int find(int x)
{
int r=x;
while(tata[r])
r=tata[r];
int y=x,t;
while(y!=r)
{
t=tata[y];
tata[y]=r;
y=t;
}
return r;
}
void Union(int x,int y)
{
if(h[x]>h[y])
tata[y]=x;
else
{
tata[x]=y;
if(h[x]==h[y])
h[y]++;
}
}
void citire()
{
int i,x,y,A,B;
f>>n>>m;
nrc=n;
for(i=1;i<=m;i++)
{
f>>x>>y;
A=find(x);
B=find(y);
if(A!=B)
{
Union(A,B);
nrc--;
}
}
f.close();
}
int main()
{
int i;
citire();
g<<nrc;
g.close();
return 0;
}