Cod sursa(job #1747444)

Utilizator flibiaVisanu Cristian flibia Data 24 august 2016 21:51:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

vector< vector < int > > v;
int n;
int m;
char viz[1000005];
int nr = 0;

void dfs(int k) {
	viz[k] = 1;
	for (int j = 0; j < v[k].size(); j++) {
		if (viz[ v[k][j] ] == 0)
			dfs(v[k][j]);
	}
	viz[k] = 2;
}

int main() {
	int a, b;
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	in >> n >> m;
	v.resize(n + 1);
	for (int i = 0; i < m; i++) {
		in >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
/*	for (int i = 1; i <= n; i++) {
		cout << i << " -> ";
		for (int j = 0; j < v[i].size(); j++) {
			cout << v[i][j] << ", ";
		}
			cout << "\n";
	}
*/
	for (int i = 1; i <= n; i++) {
		if (viz[i] == 0) {
			dfs(i);
			nr++;
		}
	}
    out << nr;
	return 0;
}