vitormartinotti

troia

Aug 7th, 2025
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAXN 500010
  3.  
  4. using namespace std;
  5.  
  6. vector<int> grafo[MAXN];
  7. int marc[MAXN];
  8.  
  9. void dfs(int v){
  10.     marc[v] = 1;
  11.     for(int i = 0; i < grafo[v].size(); i++){
  12.         int viz = grafo[v][i];
  13.         if(marc[viz] == 0){
  14.             dfs(viz);
  15.         }
  16.     }
  17. }
  18.  
  19. int main() {
  20.    
  21.     int n, m; scanf("%d %d", &n, &m);
  22.    
  23.     for(int i = 0; i < m; i++){
  24.         int a, b; scanf("%d %d", &a, &b);
  25.         grafo[a].push_back(b);
  26.         grafo[b].push_back(a);
  27.     }
  28.    
  29.     int nComp = 0; //o numero de familias eh igual ao numero de componentes
  30.     for(int v = 1; v <= n; v++){
  31.         if(marc[v] == 0){
  32.             nComp++; //conta uma componente
  33.             dfs(v);
  34.         }
  35.     }
  36.    
  37.     printf("%d\n", nComp);
  38.  
  39.     return 0;
  40. }
Tags: OBI
Advertisement
Add Comment
Please, Sign In to add comment