Josif_tepe

Untitled

Jan 10th, 2026
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 2005;
  4. int idx[maxn];
  5. int sz[maxn];
  6.  
  7. void init() {
  8.     for(int i = 0; i < maxn; i++) {
  9.         idx[i] = i;
  10.         sz[i] = 1;
  11.     }
  12. }
  13.  
  14. int find_root(int x) {
  15.     while(x != idx[x]) {
  16.         idx[x] = idx[idx[x]];
  17.         x = idx[x];
  18.     }
  19.     return x;
  20. }
  21. bool check(int A, int B) {
  22.     return find_root(A) == find_root(B);
  23. }
  24.  
  25. void unite(int A, int B) {
  26.     int rootA = find_root(A);
  27.     int rootB = find_root(B);
  28.     if(rootA != rootB) {
  29.         if(sz[rootA] < sz[rootB]) {
  30.             sz[rootB] += sz[rootA];
  31.             idx[rootA] = idx[rootB];
  32.         }
  33.         else {
  34.             sz[rootA] += sz[rootB];
  35.             idx[rootB] = idx[rootA];
  36.         }
  37.     }
  38. }
  39. int main() {
  40.     int n;
  41.     cin >> n;
  42.     init();
  43.     vector<pair<int, pair<int, int>>> graph;
  44.     for(int i = 0; i < n - 1; i++) {
  45.         int node = i + 1;
  46.         for(int j = 0; j < n - i - 1; j++) {
  47.             int cost;
  48.             cin >> cost;
  49.            
  50.             graph.push_back({cost, {i, node}});
  51.             node++;
  52.         }
  53.     }
  54.    
  55.     sort(graph.begin(), graph.end());
  56.    
  57.     vector<pair<int, int>> g[maxn];
  58.     for(int i = 0; i < (int) graph.size(); i++) {
  59.         int A = graph[i].second.first;
  60.         int B = graph[i].second.second;
  61.         int C = graph[i].first;
  62.        
  63.         if(!check(A, B)) {
  64.             unite(A, B);
  65.             g[A].push_back({B, C});
  66.             g[B].push_back({A, C});
  67.            
  68.         }
  69.     }
  70.    
  71.     for(int i = 0; i < n; i++) {
  72.         sort(g[i].begin(), g[i].end());
  73.        
  74.         cout << (int) g[i].size() << " ";
  75.         for(int j = 0; j <  (int) g[i].size(); j++) {
  76.             cout << g[i][j].first + 1 << " ";
  77.         }
  78.         cout << endl;
  79.     }
  80.    
  81.     return 0;
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment