Cod sursa(job #1610458)

Utilizator h_istvanHevele Istvan h_istvan Data 23 februarie 2016 15:59:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define FOR(i,a,b) for(int i=a; i < b; ++i)
#define MAXN 100000

using namespace std;

vector<int> graph[MAXN];
int viz[MAXN];

void dfs(int node) {
	viz[node] = 1;
	FOR(i, 0, graph[node].size()) {
		if (!viz[graph[node][i]])
			dfs(graph[node][i]);
	}
}

int main() {
	ifstream input;
	input.open("dfs.in");
	
	int n,m;
	input >> n >> m;
	
	FOR(i, 0, m) {
		int x,y;
		input >> x >> y;
		graph[x-1].push_back(y-1);
		graph[y-1].push_back(x-1);
	}
	
	input.close();
	
	int res = 0;
	FOR(i, 0, n) {
		if (!viz[i]) {
			res++;
			dfs(i);
		}
	}
	
	ofstream output;
	output.open("dfs.out");
	output << res;
	output.close();
	
	return 0;
}