Cod sursa(job #2881258)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 30 martie 2022 13:16:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(x) cout << #x <<": " << x << "\n";
#define sz(x) ((int)x.size())

using ll = long long;

const string fn = "dfs";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

int n, m;
vector<int> g[100005];
bitset<100005> viz;

void dfs(int x) {
	viz[x] = 1;
	for (int i : g[x])
		if (!viz[i])
			dfs(i);
}

int main() {

	fin >> n >> m;
	while (m--) {
		int x, y;
		fin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		if (!viz[i]) {
			dfs(i);
			ans ++;
		}
	fout << ans << "\n";
	return 0;
}