Mai intai trebuie sa te autentifici.
Cod sursa(job #2141251)
| Utilizator | Data | 24 februarie 2018 11:26:30 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 80 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.02 kb |
#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;
}
