Cod sursa(job #283441)

Utilizator MeteoraMoarteaDinCarpati Meteora Data 19 martie 2009 10:01:51
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<iostream.h>
#include<fstream.h>
int i,j,k,a[100000000][100000000],n,m,s[200000000],nr=0,x=0,v[100000000];
fstream f("dfs.in",ios::in);
fstream g("dfs.out",ios::out);
void citire(){
	f>>n;
	f>>m;
	while(x<=m){
		for(i=1;i<=2;i++)
			f>>v[i];
		a[v[1]][v[2]]=1;
		a[v[2]][v[1]]=1;		
		x++;
	}
}
void df(int nod){
	int k;
	s[nod]=1;
    for(k=1;k<=n;k++)
        if(a[nod][k]==1 && s[k]==0)
            df(k);
}
int main(){ 	
	citire();
    df(1);
    for(i=1;i<=n;i++)
        if(s[i]==0){
            df(s[i]);
			nr++;
		}
	g<<nr;
    return 0;
}