Cod sursa(job #2158852)

Utilizator flibiaVisanu Cristian flibia Data 10 martie 2018 16:45:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
//DSU 
#pragma GCC optimize("03")
#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, dad[100100], cnt;
bool viz[100100];

int find(int x){
	return (x == dad[x] ? x : dad[x] = find(dad[x]));
}

void join(int x, int y){
	dad[find(x)] = find(y);
}

int main(){
	ios_base::sync_with_stdio(0);
	in.tie(NULL);
	in >> n >> m;
	for(int i = 1; i <= n; i++)
		dad[i] = i;
	for(int i = 1; i <= m; i++){
		in >> x >> y;
		join(x, y);
	}
	for(int i = 1; i <= n; i++){
		find(i);
		if(!viz[dad[i]]){
			cnt++;
			viz[dad[i]] = 1;
		}
	}
	out << cnt;
	return 0;
}