CCCPaste

Untitled

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2005;
int parent[maxn];
int sz[maxn];

void init() {
    for(int i = 0; i < maxn; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}
int find_root(int x) {
    while(x != parent[x]){
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}
void unite(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    
    if(root_a != root_b) {
        if(sz[root_a] < sz[root_b]) {
            sz[root_b] += sz[root_a];
            parent[root_a] = parent[root_b];
        }
        else {
            sz[root_a] += sz[root_a];
            parent[root_b] = parent[root_a];
        }
    }
}
bool check(int a, int b) {
    return find_root(a) == find_root(b);
}
vector > g[maxn];
int main() {
    ios_base::sync_with_stdio(false);
    init();
    int n;
    cin >> n;
    
    vector > >  graph;
    for(int i = 0; i < n - 1; i++) {
        int node = i + 1;
        for(int j = 0; j < n - i - 1; j++) {
            int x;
            cin >> x;
            graph.push_back(make_pair(x, make_pair(i, node)));
            node++;
        }
    }
    
    sort(graph.begin(), graph.end());
    
    for(int i = 0; i < (int) graph.size(); i++) {
        int a = graph[i].second.first;
        int b = graph[i].second.second;
        int c = graph[i].first;
        
        if(!check(a, b)) {
            unite(a, b);
            g[a].push_back(make_pair(b, c));
            g[b].push_back(make_pair(a, c));
        }
        
    }
    for(int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
        cout << (int) g[i].size() << " ";
        for(int j = 0; j < g[i].size(); j++) {
            cout << g[i][j].first + 1 << " " ;
        }
        cout << endl;
    }
    return 0;
}