Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #define MAX 10020
- using namespace std;
- int n, m, pai[MAX];
- set<int> fam;
- int find(int a){ // serve para retornar o patriarca da familia
- if(pai[a] == a){ // se o pai de a for ele mesmo, retorna ele;
- return a;
- }
- return pai[a] = find(pai[a]);
- }
- void join(int a, int b){
- pai[find(a)] = find(b);
- }
- int main(){
- cin >> n >> m;
- int a, b;
- //iniciar cada um como pai de si mesmo
- for(int i = 0; i < n; i++){
- pai[i] = i;
- }
- for(int i = 0; i < m; i++){
- cin >> a >> b;
- join(a, b);
- }
- for(int i = 1; i <= n; i++){
- fam.insert(find(i));
- }
- cout << fam.size() << "\n";
- // O VETOR PAI PEGA O PAI IMEDIATO E O PAI MAXIMO É COM O FIND
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement