Cod sursa(job #372561)
| Utilizator | Data | 10 decembrie 2009 20:03:52 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 30 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.47 kb |
#include<fstream>
using namespace std;
int n,m,t[100002],nrc;
int rad(int x)
{
while(t[x])
x=t[x];
return x;
}
void reuniune(int x,int y)
{
if(rad(x)!=rad(y))
{
t[x]=rad(y);
nrc--;
}
}
int main()
{
ifstream fin("dfs.in");
fin>>n>>m;
nrc=n;
for( ; m ;m--)
{
int i,j;
fin>>i>>j;
reuniune(i,j);
}
ofstream fout("dfs.out");
fout<<nrc;
return 0;
}
