Cod sursa(job #2041944)

Utilizator Spiromanii_MessiUNIBUCThrowTerror Spiromanii_Messi Data 17 octombrie 2017 21:39:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <vector>
#include <fstream>
#include <queue>
#include <bitset>
using namespace std ;

const int MAX = 1e5 + 14 ;

bitset <MAX> viz ; 
vector < vector<int> > gr (MAX + 1); 
void dfs (int nod) {
	viz [nod] = 1 ; 
	for (auto &x : gr [nod]) {
		if (viz [x] == 0) dfs (x) ; 
	}
}

int main(int argc, char const *argv[])
{
	ifstream cin ("dfs.in") ;
	ofstream cout ("dfs.out") ; 
	int n, m, source ;
	cin >> n >> m; 
	
	while (m --) {
		int x, y ; 
		cin >> x >> y ; 
		gr [x].push_back (y) ; 
		gr [y].push_back (x) ; 
	}
	int cate = 0 ; 
	for (int i = 1 ; i <= n ; ++ i) {
		if (viz [i]) continue ;
		cate += 1 ; 
		dfs (i) ; 
	}
	cout << cate ; 
	return 0;
}