Cod sursa(job #444203)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 19 aprilie 2010 18:40:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
#include <vector>
#define MAXN 101000

using namespace std;
vector<int> G[MAXN];
int i,n,m,x,y;
bool ok[MAXN];

void df(int nod)
{
	ok[nod] = true;
	vector<int>::iterator it;
	for (it=G[nod].begin(); it!=G[nod].end(); it++)
		if (!ok[*it])
			df(*it);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1; i<=m; i++){
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	m=0;
	for (i=1; i<=n; i++)
		if (!ok[i]){
			df(i);
			m++;
		}
	printf("%d\n",m);
	return 0;
}