Cod sursa(job #372563)
Utilizator | Csorba Lorand-Alexandru lorand | Data | 10 decembrie 2009 20:06:08 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.44 kb |
using namespace std;
#include<fstream>
int n,m,nrc,t[100000];
int radacina(int x)
{
while(t[x])x=t[x];
return x;
}
void reuniune(int x,int y)
{
if(radacina(x)!=radacina(y))
{
t[x]=radacina(y);
nrc--;
}
}
int main()
{
int i,x,y;
ifstream fin("dfs.in");
fin>>n>>m;
nrc=n;
for(i=1;i<=m;i++)
{
fin>>x>>y;
reuniune(x,y);
}
fin.close();
ofstream fout("dfs.out");
fout<<nrc;
fout.close();
return 0;
}