#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define pb push_back const int N=1050; vector<int> E[N]; void AddEdge(int u,int v){E[u].pb(v),E[v].pb(u);} bool was[N]; vector<int> Euler; vector<vector<int>> p; void DFS(int u){ was[u]=true,Euler.pb(u); for(int v:E[u])if(!was[v]&&p[u][v]==1)DFS(v); } void DFS1(int u){ was[u]=true,Euler.pb(u); for(int v:E[u])if(!was[v]&&p[u][v]==2)DFS1(v); } int construct(vector<vector<int>> P){ p=P;int n=(int)p.size(); 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;j<n;j++)if(p[i][j]>0)AddEdge(i,j); bool one=false,two=false; for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==1)one=true; for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==2)two=true; vector<vector<int>> ans(n,vector<int>(n,0)); if(!one&&!two){ build(ans); return 1; } vector<int> root; for(int i=0;i<n;i++){ if(!was[i]){ DFS(i); if((int)Euler.size()==1){ Euler.clear(); continue; } for(int x:Euler)for(int y:Euler)if(x!=y&&p[x][y]==0)return 0; root.pb(i); for(int j=1;j<(int)Euler.size();j++){ int x=Euler[j],y=Euler[j-1]; ans[x][y]=ans[y][x]=1; } Euler.clear(); } } if(one&&!two){ build(ans); return 1; } for(int i=0;i<n;i++)was[i]=false; if(two&&!one){ for(int i=0;i<n;i++){ if(!was[i]){ DFS1(i); if((int)Euler.size()==1){ Euler.clear(); continue; } if((int)Euler.size()==2)return 0; for(int j=1;j<(int)Euler.size();j++){ int x=Euler[j],y=Euler[j-1]; ans[x][y]=ans[y][x]=1; } for(int x:Euler)for(int y:Euler)if(x!=y&&p[x][y]==0)return 0; if((int)Euler.size()>2){ int x=Euler[0],y=Euler.back(); ans[x][y]=ans[y][x]=1; } Euler.clear(); } } build(ans); return 1; } if(one&&two&&(int)root.size()==2)return 0; for(int i=1;i<(int)root.size();i++){ int x=root[i],y=root[i-1]; ans[x][y]=ans[y][x]=1; } for(int x:root)for(int y:root)if(x!=y&&p[x][y]==0)return 0; int x=root[0],y=root.back(); ans[x][y]=ans[y][x]=1; build(ans); return 1; }