Pagini recente » Cod sursa (job #326468) | Cod sursa (job #1411438) | Cod sursa (job #2425335) | Cod sursa (job #552955) | Cod sursa (job #2141251)
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int tata[100000], niv[100000];
int fnd(int x)
{
int y = x, r = x;
while(tata[r] != 0)
{
r = tata[r];
}
while(tata[y] != 0)
{
int z = tata[y];
tata[y] = r;
y = z;
}
return r;
}
void uni(int x, int y)
{
int t1 = fnd(x), t2 = fnd(y);
if(t1 != t2)
{
if(niv[t1] < niv[t2])
{
tata[t1] = t2;
}
else
{
tata[t2] = t1;
}
if(niv[t1] == niv[t2]){
tata[t2] = t1;
niv[t1]++;
}
}
}
int main()
{
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
uni(fnd(a), fnd(b));
}
int nr = 0;
for(int i = 1; i <= n; i++)
{
if(tata[i] == 0)
{
nr++;
}
}
fout << nr;
return 0;
}