Advertisement
Josif_tepe

Untitled

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