#include <iostream> #include <vector> #include "supertrees.h" using namespace std; int n; vector<int> sz; vector<int> par; int find(int st){ if( st != par[st] ) return par[st] = find(par[st]); return st; } void connect(int a, int b){ a = find(a); b = find(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); par[b] = a; sz[a] += sz[b]; } int construct(vector<vector<int>> p){ n = p.size(); sz.assign(n, 1); par.assign(n, 0); for(int i = 0; i<n; i++) par[i] = i; for(int i = 0; i<n; i++){ for(int j = 0; j<n; j++){ if(p[i][j]) connect(i, j); } } for(int i = 0; i<n; i++){ for(int j = 0; j<n; j++){ if(!p[i][j] && (find(i) == find(j))){ //cout<<-1<<endl; return 0; } } } vector<vector<int>> ans; ans.assign(n, vector<int>(n, 0)); for(int i = 0; i<n; i++){ if(i!=find(i)){ ans[i][par[i]] = 1; ans[par[i]][i] = 1; } } build(ans); // for(int i = 0; i<n; i++){ // for(int j = 0; j<n; j++){ // cout<<ans[i][j]<<' '; // } // cout<<endl; // } return 1; }