reinos.cpp

#include <bits/stdc++.h>
#define maxn 100010

using namespace std;
vector<int> grafo[maxn];
int n, m;
int c, mark[maxn];

void dfs(int u) { // DFS para marcar todos os caras na componente
	for(int i = 0; i < (int)grafo[u].size(); i++) {
		int v = grafo[u][i];
		if(mark[v] == 0) {
			mark[v] = mark[u]; // Faço a componente de v ser a mesma de u
			dfs(v);
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i=1;i<=m;i++) {
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		if(mark[i] == 0) { // Caso i nao tenha componente calculada ainda
			c++; // Aumento o numero de componentes
			mark[i] = c; // Faço i receber a componente atual
			dfs(i); // Marco os vizinhos de u com a mesma componente de u
		}
	}
	cout << c-1 << "\n"; // Numero de componentes - 1
	return 0;
}