#include<bits/stdc++.h> #include "supertrees.h" #define ll long long #define ld long double #define vl vector<ll> #define vi vector<int> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define sz(v) (int)(v.size()) #define f first #define s second #define pii pair<int, int> #define pll pair<ll, ll> using namespace std; const int sz = 1e3+5; int usize[sz], par[sz]; void makeset(int v) { par[v] = v; usize[v] = 1; } int findpar(int v) { if(par[v] == v) return v; return par[v] = findpar(par[v]); } void unionsets(int a, int b) { a = findpar(a); b = findpar(b); if(a != b) { if(usize[a] > usize[b]) swap(a, b); par[b] = a; usize[a] += usize[b]; } } int construct(vector<vector<int>>p) { int n = sz(p); for(int i = 0; i < n; i++) makeset(i); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(p[i][j] == 2) unionsets(i, j); } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(p[i][j]) continue; int u = i, v = j; u = findpar(u); v = findpar(v); if(u == v) { return 0; } } } int grid[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) grid[i][j] = 0; } vi v[n]; for(int i = 0; i < n; i++) { int u = i; u = findpar(u); v[u].pb(i); } for(int i = 0; i < n; i++) { if(sz(v[i]) > 2) { for(int j = 0; j < sz(v[i]); j++) { int nxt = (j + 1) % sz(v[i]); grid[v[i][nxt]][v[i][j]] = 1; grid[v[i][j]][v[i][nxt]] = 1; } } if(sz(v[i]) == 2) { return 0; } } vector<vector<int>>answer; for(int i = 0; i < n; i++) { vector<int>row; for(int j = 0; j < n; j++) row.pb(grid[i][j]); answer.pb(row); } build(answer); return 1; }