Cod sursa(job #493068)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 16 octombrie 2010 21:35:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
// adancime pt a determina nr de componente conexe

#include<cstdio>

using namespace std;

const int Nmax = 100001;

struct graf {
	int nod;
	graf *leg;
};

graf *G[Nmax];
char viz[Nmax];
int N, M, sol;

void add(int x, int y) {
	graf *p;
	p=new graf;
	p->leg=G[x];
	p->nod=y;
	G[x]=p;
}

void dfs(int nod) {
	viz[nod]=1;
	graf *p;
	for(p=G[nod]; p; p=p->leg) 
		if(!viz[p->nod])
			dfs(p->nod);
}

int main() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	int i, j;
	
	scanf("%d %d",&N,&M);
	while(M--) {
		scanf("%d %d",&i,&j);
		add(i,j);
		add(j,i);
	}
	
	for(i=1; i<=N; i++)
		if(!viz[i]) {
			dfs(i);
			sol++;
		}
	
	printf("%d\n",sol);
	
	return 0;
}