#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define pb push_back const int N=1050; vector<int> E[N]; vector<vector<int>> p,ans(N,vector<int>(N,0)); void AddEdge(int u,int v){E[u].pb(v);E[v].pb(u);} bool was[N]; vector<int> euler; void DFS1(int u){ was[u]=true; euler.pb(u); for(int e:E[u])if(!was[e]&&p[u][e]==1)DFS1(e); } void DFS2(int u){ was[u]=true; euler.pb(u); for(int e:E[u])if(!was[e]&&p[u][e]==2)DFS2(e); } int construct(vector<vector<int>> P){ int n=(int)P.size();p=P; ans.resize(n); for(int i=0;i<n;i++)ans[i].resize(n); for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==3)return 0; for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(p[i][j]>0)AddEdge(i,j); for(int i=0;i<n;i++)if(!was[i]){ DFS1(i); for(int x:euler)for(int y:euler)if(x!=y&&p[x][y]==0)return 0; for(int i=1;i<(int)euler.size();i++){ int from=euler[i],to=euler[i-1]; ans[from][to]=ans[to][from]=1; } euler.clear(); } memset(was,false,sizeof(was)); for(int i=0;i<n;i++)if(!was[i]){ DFS2(i); if((int)euler.size()==1){ euler.clear(); continue; } if((int)euler.size()==2)return 0; for(int x:euler)for(int y:euler)if(x!=y&&p[x][y]==0)return 0; for(int i=1;i<(int)euler.size();i++){ int from=euler[i],to=euler[i-1]; ans[from][to]=ans[to][from]=1; } int from=euler[0],to=euler.back(); ans[from][to]=ans[to][from]=1; euler.clear(); } build(ans); return 1; }