Cod sursa(job #361103)

Utilizator digital_phreakMolache Andrei digital_phreak Data 3 noiembrie 2009 18:51:40
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100010
using namespace std;

vector <int> A[MAXN];
int vis[MAXN];
int N,M,nrcon;

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

void DFS(int x) {
	int i;
	vis[x] = 1;
	for (i=1;i<=A[x][0];++i) {
		if (!vis[A[x][i]]) DFS(A[x][i]);
	}
}

int main() {

	int x,y,i;

	nrcon = 0;
	
	fin >> N >> M;
	
	for (i=1;i<=N;++i) {
		A[i].push_back(0);
	}
	
	for (i=1;i<=M;++i) {
		fin >> x >> y;
		A[x].push_back(y);
		A[y].push_back(x);
		++A[x][0];
	}
	
	for (i=1;i<=N;++i) {
		if (!vis[i]) {
			DFS(i);
			nrcon++;
		}
	}
	
	fout << nrcon << endl;

	fin.close();
	fout.close();
	return 0;
}