Cod sursa(job #594246)

Utilizator informatician28Andrei Dinu informatician28 Data 6 iunie 2011 18:49:17
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<fstream> 
using namespace std; 
ifstream f("dfs.in");
ofstream g("dfs.out");
int t[2][150000],start[150000],viz[150000];
void df(int nod) 
{int p; 
p=start[nod];
viz[nod]=1; 
while(p) 
{if(viz[t[0][p]]==0) 
	df(t[0][p]); 
p=t[1][p]; 
}
}
int main() 
{int n,m,a,i,j,k=0,nr=0;
	f>>n>>m; 
for(a=1;a<=m;a++) 
{f>>i>>j;
	k++; 
t[0][k]=j; 
t[1][k]=start[i]; 
start[i]=k; 
k++; 
t[0][k]=i; 
t[1][k]=start[j]; 
start[j]=k; 
}
for(i=1;i<=n;i++) 
	if(viz[i]==0) 
		{df(i); nr++; } 
g<<nr;
		return 0; 
}