Cod sursa(job #394110)

Utilizator preda_alexandruPreda Alexandru preda_alexandru Data 10 februarie 2010 16:14:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<iostream.h>
#include<fstream.h>

ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct nod {
			int x;
			nod *next;
		    };

int i,n,m,sel[100001],nrc;
nod *v[100001];
		   
void citire()
{
int i,l1,l2;
nod *p;
fin>>n>>m;
for(i=1;i<=m;i++){
				 fin>>l1>>l2;
				 p=new nod;
				 p->x=l2;
				 p->next=v[l1];
				 v[l1]=p;
		 		
				 p=new nod;
				 p->x=l1;
				 p->next=v[l2];
				 v[l2]=p;
				}
}

void dfs(int s)
{
nod *p=v[s];
sel[s]=nrc;
while(p){
		if(!sel[p->x])dfs(p->x);
		p=p->next;
		}
}

int main()
{
citire();
for(i=1;i<=n;i++)if(!sel[i]){
							nrc++;
							dfs(i);
							}
fout<<nrc;
return 0;
}