Advertisement
vitormartinotti

Untitled

Mar 13th, 2025
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define MAXN 10010
  3.  
  4. using namespace std;
  5.  
  6. vector<int> grafo[MAXN];
  7. int marc[MAXN], sub[MAXN], nivel[MAXN], peso[MAXN];
  8.  
  9. void dfs(int v){
  10.  
  11.     marc[v] = 1;
  12.     sub[v] = 1;
  13.  
  14.     for(int i = 0; i < grafo[v].size(); i++){
  15.         int viz = grafo[v][i];
  16.         if (marc[viz] == 0){
  17.             nivel[viz] = nivel[v] + 1;
  18.             dfs(viz);
  19.             sub[v] += sub[viz];
  20.         }
  21.     }
  22. }
  23.  
  24. bool bal (int v){
  25.  
  26.     if (grafo[v].size() == 0){
  27.         return true;
  28.     }
  29.  
  30.     int atual_sub = sub[grafo[v][0]];
  31.     for (int i = 0; i < grafo[v].size(); i++){
  32.         int viz = grafo[v][i];
  33.         if (atual_sub != sub[viz]){
  34.             return false;
  35.         }
  36.     }
  37.  
  38.     int prox = grafo[v][0];
  39.     return bal(prox);
  40. }
  41.  
  42. int main (){
  43.     int n; scanf("%d", &n);
  44.  
  45.     for (int i = 0; i < n; i++){
  46.         int a, b; scanf("%d %d", &a, &b);
  47.         grafo[b].push_back(a);
  48.     }
  49.  
  50.     dfs(0);
  51.  
  52.     if(bal(0)){
  53.         cout << "bem" << endl;
  54.    }else{
  55.         cout << "mal" << endl;
  56.    }
  57.  
  58.  
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement