class DSU:
def __init__(self, n: int):
self.n = n
self.parent = list(range(n + 1))
self.size = [1] * (n + 1)
def find(self, u: int) -> int:
if u == self.parent[u]:
return u
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u: int, v: int):
u, v = self.find(u), self.find(v)
if u != v:
if self.size[u] < self.size[v]:
u, v = v, u
self.parent[v] = u
self.size[u] += self.size[v]
def solve():
n = int(input())
dsu = DSU(n)
removes = []
for _ in range(n - 1):
u, v = map(int, input().split())
pu, pv = dsu.find(u), dsu.find(v)
if pu == pv:
removes.append((u, v))
dsu.union(pu, pv)
uniques = list(set([dsu.find(i) for i in range(1, n + 1)]))
sz = len(uniques)
if sz < 2:
print(0)
return
else:
print(sz - 1)
for i in range(sz - 1):
day = [removes[i][0], removes[i][1], uniques[i], uniques[i+1]]
print(*day)
solve()
#include <bits/stdc++.h>
using namespace std;
class DSU {
public:
vector<int> P;
vector<int> rank;
DSU(int n) {
P.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
P[i] = i;
}
}
void join(int u, int v) {
int pu = P[u];
int pv = P[v];
if (pu == pv) {
return;
}
if (rank[pu] < rank[pv]) {
swap(pu, pv);
}
if (rank[pu] == rank[pv]) {
rank[pu]++;
}
P[pv] = pu;
}
int get(int u) {
if (P[u] != u) {
P[u] = get(P[u]);
}
return P[u];
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
DSU dsu(n + 1);
vector<vector<int>> ans;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
if (dsu.get(u) != dsu.get(v)) {
dsu.join(u, v);
} else {
vector<int> spare = {u, v, 0, 0};
ans.push_back(spare);
}
}
int k = 0;
for (int i = 1; i < n; i++) {
if (dsu.get(i) != dsu.get(i + 1)) {
dsu.join(i, i + 1);
ans[k][2] = i;
ans[k][3] = i + 1;
k++;
}
}
cout << k << "\n";
for (auto &row : ans) {
for (int a : row) {
cout << a << " ";
}
cout << "\n";
}
}1629B - GCD Arrays | 1629A - Download More RAM |
1629C - Meximum Array | 1629D - Peculiar Movie Preferences |
1629E - Grid Xor | 1629F1 - Game on Sum (Easy Version) |
2148. Count Elements With Strictly Smaller and Greater Elements | 2149. Rearrange Array Elements by Sign |
2150. Find All Lonely Numbers in the Array | 2151. Maximum Good People Based on Statements |
2144. Minimum Cost of Buying Candies With Discount | Non empty subsets |
1630A - And Matching | 1630B - Range and Partition |
1630C - Paint the Middle | 1630D - Flipping Range |
1328A - Divisibility Problem | 339A - Helpful Maths |
4A - Watermelon | 476A - Dreamoon and Stairs |
1409A - Yet Another Two Integers Problem | 977A - Wrong Subtraction |
263A - Beautiful Matrix | 180C - Letter |
151A - Soft Drinking | 1352A - Sum of Round Numbers |
281A - Word Capitalization | 1646A - Square Counting |
266A - Stones on the Table | 61A - Ultra-Fast Mathematician |