Pagini recente » Cod sursa (job #2526911) | Cod sursa (job #3169374) | Cod sursa (job #1561505) | Cod sursa (job #645117) | Cod sursa (job #2125276)
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n;
vector<int> T, Rang;
int Radacina(int k)
{
int x = k;
while(T[x] != 0)
x = T[x];
while(T[k] && T[k] != x)
{
int y = T[k];
T[k] = x;
k = y;
}
return x;
}
int main()
{
fin >> n;
Rang = T = vector<int> (n + 1 , 0);
int i ,j;
while(fin >> i >> j)
{
int ri = Radacina(i), rj = Radacina(j);
if(ri != rj)
{
if(Rang[ri] > Rang[rj])
T[rj] = ri;
else
{
T[ri] = rj;
if(Rang[ri] == Rang[rj])
Rang[rj] ++;
}
}
}
int nrc = 0;
for(auto x : T)
if(x == 0)
nrc ++;
fout << nrc - 1;
fin.close();
fout.close();
return 0;
}