Advertisement
Guest User

Untitled

a guest
Jun 24th, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. /// Defines
  6. #define all(a) a.begin(),a.end()
  7. #define ios std::ios::sync_with_stdio(false);
  8.  
  9. /// STL
  10. #define vi vector<int>
  11. #define vvi vector< vector<int> >
  12. #define pb push_back
  13. #define mp make_pair
  14. #define mii map<int,int>
  15. #define pii pair<int,int>
  16.  
  17. /// Iterator
  18. #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
  19.  
  20. /// Constants
  21. #define ll long long
  22. #define mod 1000000007
  23. #define EPS 1e-7
  24.  
  25. /// File I/O
  26. #define READ(f) freopen(f, "r", stdin)
  27. #define WRITE(f) freopen(f, "w", stdout)
  28.  
  29. using namespace std;
  30.  
  31. struct DisjointSet
  32. {
  33.     /// Declarations
  34.     int* parent;
  35.     int connectedComp;
  36.     bool connCompNodes[1100];
  37.  
  38.     /// Constructor.
  39.     DisjointSet(int n)
  40.     {
  41.         parent = new int[n];
  42.         connectedComp = n;
  43.         for(int i = 0 ; i < n ; i++)
  44.         {
  45.             parent[i] = i;
  46.             connCompNodes[i] = true;
  47.         }
  48.     }
  49.  
  50.     int findParent(int node)
  51.     {
  52.         if(parent[node] == node)
  53.             return node;
  54.         return parent[node] = findParent(parent[node]);
  55.     }
  56.  
  57.     /// Returns false if the 2 nodes are already connected, indicating that if we want to connect them again it would generate a cycle.
  58.     bool mergeNodes(int a, int b)
  59.     {
  60.         int parentA = findParent(a);
  61.         int parentB = findParent(b);
  62.         if(parentA == parentB)
  63.             return false;
  64.         parent[parentB] = parentA; /// A is the grandParent now
  65.         connectedComp--;
  66.         connCompNodes[parentB] = false;
  67.         return true;
  68.     }
  69.  
  70.     int connectedComponents()
  71.     {
  72.         return connectedComp;
  73.     }
  74. };
  75.  
  76. struct plan {
  77.     int i, j, u, v;
  78. } plan[5000];
  79.  
  80. int main()
  81. {
  82.     int n, t = 0;
  83.     cin >> n;
  84.  
  85.     struct DisjointSet dsu(n);
  86.  
  87.     for (int i = 0; i < n - 1; i++)
  88.     {
  89.         int x, y;
  90.         cin >> x >> y;
  91.  
  92.         x--, y--;
  93.         if(!dsu.mergeNodes(x, y))
  94.         {
  95.             plan[t].i = x+1;
  96.             plan[t].j = y+1;
  97.             t++;
  98.         }
  99.     }
  100.  
  101.     int f = 0, uCount = 0, vCount = 0;
  102.     for (int i = 0; i < n; i++)
  103.     {
  104.         if (dsu.connCompNodes[i] == true)
  105.         {
  106.             if (f != 0)
  107.             {
  108.                 plan[vCount].v = i+1;
  109.                 vCount++;
  110.             }
  111.             plan[uCount].u = i+1;
  112.             uCount++;
  113.             f = 1;
  114.         }
  115.     }
  116.  
  117.     cout << t << endl;
  118.     for (int i = 0; i < t; i++)
  119.         cout << plan[i].i << " " << plan[i].j << " " << plan[i].u << " " << plan[i].v << endl;
  120.  
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement