Cod sursa(job #2125276)

Utilizator titusuTitus C titusu Data 8 februarie 2018 12:34:15
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#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;

}