SHARE
TWEET

Spanning_Tree_OF

a guest Feb 16th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define nmax 30003
  3. using namespace std;
  4.  
  5. vector<int> L[nmax];
  6. int n, d[nmax];
  7. int st[nmax], top;
  8.  
  9. void Citire()
  10. {
  11.     int i, j;
  12.     cin >> n;
  13.     while (cin >> i >> j)
  14.     {
  15.         L[i].push_back(j);
  16.         L[j].push_back(i);
  17.         d[i]++;
  18.         d[j]++;
  19.     }
  20. }
  21.  
  22. void Rezolva()
  23. {
  24.     int i, cnt;
  25.     for (i = 1; i <= n; i++)
  26.         if (d[i] == 1)
  27.             st[++top] = i;
  28.     while (top > 0)
  29.     {
  30.         i = st[top--];
  31.         for (auto j : L[i])
  32.             if (d[j] != 1)
  33.             {
  34.                 d[j]--;
  35.                 if (d[j] == 1)
  36.                     st[++top] = j;
  37.             }
  38.     }
  39.     cnt = 0;
  40.     for (i = 1; i <= n; i++)
  41.         if (d[i] > 1) cnt++;
  42.     cout << cnt << "\n";
  43. }
  44.  
  45. int main()
  46. {
  47.     Citire();
  48.     Rezolva();
  49.     return 0;
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top