Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <stdio.h>
- #include <stdlib.h>
- /// Defines
- #define all(a) a.begin(),a.end()
- #define ios std::ios::sync_with_stdio(false);
- /// STL
- #define vi vector<int>
- #define vvi vector< vector<int> >
- #define pb push_back
- #define mp make_pair
- #define mii map<int,int>
- #define pii pair<int,int>
- /// Iterator
- #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
- /// Constants
- #define ll long long
- #define mod 1000000007
- #define EPS 1e-7
- /// File I/O
- #define READ(f) freopen(f, "r", stdin)
- #define WRITE(f) freopen(f, "w", stdout)
- using namespace std;
- struct DisjointSet
- {
- /// Declarations
- int* parent;
- int connectedComp;
- bool connCompNodes[1100];
- /// Constructor.
- DisjointSet(int n)
- {
- parent = new int[n];
- connectedComp = n;
- for(int i = 0 ; i < n ; i++)
- {
- parent[i] = i;
- connCompNodes[i] = true;
- }
- }
- int findParent(int node)
- {
- if(parent[node] == node)
- return node;
- return parent[node] = findParent(parent[node]);
- }
- /// Returns false if the 2 nodes are already connected, indicating that if we want to connect them again it would generate a cycle.
- bool mergeNodes(int a, int b)
- {
- int parentA = findParent(a);
- int parentB = findParent(b);
- if(parentA == parentB)
- return false;
- parent[parentB] = parentA; /// A is the grandParent now
- connectedComp--;
- connCompNodes[parentB] = false;
- return true;
- }
- int connectedComponents()
- {
- return connectedComp;
- }
- };
- struct plan {
- int i, j, u, v;
- } plan[5000];
- int main()
- {
- int n, t = 0;
- cin >> n;
- struct DisjointSet dsu(n);
- for (int i = 0; i < n - 1; i++)
- {
- int x, y;
- cin >> x >> y;
- x--, y--;
- if(!dsu.mergeNodes(x, y))
- {
- plan[t].i = x+1;
- plan[t].j = y+1;
- t++;
- }
- }
- int f = 0, uCount = 0, vCount = 0;
- for (int i = 0; i < n; i++)
- {
- if (dsu.connCompNodes[i] == true)
- {
- if (f != 0)
- {
- plan[vCount].v = i+1;
- vCount++;
- }
- plan[uCount].u = i+1;
- uCount++;
- f = 1;
- }
- }
- cout << t << endl;
- for (int i = 0; i < t; i++)
- cout << plan[i].i << " " << plan[i].j << " " << plan[i].u << " " << plan[i].v << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement