Cod sursa(job #1954606)

Utilizator dica69Alexandru Lincan dica69 Data 5 aprilie 2017 15:29:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>
#include <list>
 
using namespace std;
 
vector<list<int>> a(100001);
int use[100001];
int n, m, i, x, y, k;
 
void dfs(int node) {
	use[node] = 1;
	for (auto it : a[node]) {
		if (!use[it]) {
			dfs(it);
		} 
	} 
 }

int main() {
	FILE *f1 = fopen("dfs.in", "r");
	FILE *f2 = fopen("dfs.out", "w");
	fscanf(f1, "%d%d", &n, &m);

	for (i = 1; i <= m; i++) {
		fscanf(f1,"%d %d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}

	for (i = 1; i <= n; i++) { 
		if (!use[i]) {
			k++;
			dfs(i);
		}
	}

	fprintf(f2, "%d", k);
	
	fclose(f1);
	fclose(f2);

    return 0;
}