Cod sursa(job #873362)

Utilizator RobertBBadea Corneliu Robert RobertB Data 7 februarie 2013 09:35:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int N, M;
int nr;
bool A[100021];
vector <int> v[100010];

void DFS(int x)
{
	int Size = v[x].size();
	A[x] = 1;
	for(int i = 0; i < Size; i++) {
		if(A[v[x][i]] == 0) {
			DFS(v[x][i]);
		}
	}
}

int main()
{
	int a,b;
	f >> N;
	f >> M;
	for(int i = 1; i <= M; i++) {
		f >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i = 1; i <= N; i++) {
		if(!A[i]) {
			nr++;
			DFS(i);
		}
	}
	g << nr;
	
}