Advertisement
Guest User

oiee

a guest
Nov 12th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #define MAX 10020
  4.  
  5. using namespace std;
  6.  
  7. int n, m, pai[MAX];
  8. set<int> fam;
  9.  
  10. int find(int a){ // serve para retornar o patriarca da familia
  11.  
  12.     if(pai[a] == a){ // se o pai de a for ele mesmo, retorna ele;
  13.         return a;
  14.     }
  15.  
  16.     return pai[a] = find(pai[a]);
  17. }
  18.  
  19. void join(int a, int b){
  20.  
  21.     pai[find(a)] = find(b);    
  22.    
  23. }
  24.  
  25. int main(){
  26.  
  27.     cin >> n >> m;
  28.     int a, b;    
  29.  
  30.     //iniciar cada um como pai de si mesmo
  31.     for(int i = 0; i < n; i++){
  32.         pai[i] = i;
  33.     }
  34.  
  35.     for(int i = 0; i < m; i++){
  36.         cin >> a >> b;
  37.  
  38.         join(a, b);
  39.     }
  40.    
  41.     for(int i = 1; i <= n; i++){
  42.         fam.insert(find(i));
  43.     }
  44.  
  45.     cout << fam.size() << "\n";    
  46.     // O VETOR PAI PEGA O PAI IMEDIATO E O PAI MAXIMO É COM O FIND
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement