#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
typedef long long ll;
vector<int> jedan[1010], dva[1010];
bool check[1010];
int components[1010];
vector<int>lin, cc;
map<int, pair<int, int> >comp;
bool provera(int x, std::vector<std::vector<int>>p, int cmp)
{
components[x]=cmp;
lin.push_back(x);
int n=p.size();
for(int i=0; i<jedan[x].size(); i++)
{
if(check[jedan[x][i]])continue;
check[jedan[x][i]]=true;
components[jedan[x][i]]=cmp;
for(int j=0; j<n; j++)
{
if(p[jedan[x][i]][j]!=p[x][j])return false;
}
}
for(int i=0; i<dva[x].size(); i++)
{
if(check[dva[x][i]])continue;
check[dva[x][i]]=true;
components[dva[x][i]]=cmp;
for(int j=0; j<n; j++)
{
bool g1=false, g2=false;
if(p[dva[x][i]][j]!=0)g1=true;
if(p[x][j]!=0)g2=true;
if(g1^g2)return false;
}
if(!provera(dva[x][i], p, cmp))return false;
}
return true;
}
int construct(std::vector<std::vector<int>>p)
{
int n=p.size();
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(p[i][j]==1)jedan[i].push_back(j);
else if(p[i][j]==2)dva[i].push_back(j);
else if(p[i][j]==3)return 0;
}
}
for(int i=0; i<n; i++)
{
if(check[i])continue;
comp[i]={-1, 0};
cc.push_back(i);
if(!provera(i, p, i))return 0;
}
int ans[n][n]={0};
for(int i=0; i<n; i++)for(int j=0; j<n; j++)ans[i][j]=0;
for(int i=0; i<lin.size(); i++)
{
for(int j=1; j<jedan[lin[i]].size(); j++)
{
ans[jedan[lin[i]][j]][jedan[lin[i]][j-1]]=1;
ans[jedan[lin[i]][j-1]][jedan[lin[i]][j]]=1;
}
}
for(int i=0; i<lin.size(); i++)
{
int c=components[lin[i]];
cout<<lin[i]<<" "<<c<<endl;
if(comp[c].first==-1)comp[c]={lin[i], lin[i]};
else
{
ans[comp[c].second][lin[i]]=1;
ans[lin[i]][comp[c].second]=1;
comp[c].second=lin[i];
}
}
for(int i=0; i<cc.size(); i++)
{
ans[comp[cc[i]].first][comp[cc[i]].second]=1;
ans[comp[cc[i]].second][comp[cc[i]].first]=1;
}
for(int i=0; i<n; i++)
{
ans[i][i]=0;
}
build(ans);
return 1;
}
/*int main()
{
int n; cin>>n;
vector<vector<int> >p;
for(int i=0; i<n; i++)
{
vector<int>pp(n);
for(int j=0; j<n; j++)
{
cin>>pp[j];
}
p.push_back(pp);
}
cout<<construct(p);
}*/
Compilation message
supertrees.cpp: In function 'bool provera(int, std::vector<std::vector<int> >, int)':
supertrees.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0; i<jedan[x].size(); i++)
| ~^~~~~~~~~~~~~~~~
supertrees.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0; i<dva[x].size(); i++)
| ~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<lin.size(); i++)
| ~^~~~~~~~~~~
supertrees.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int j=1; j<jedan[lin[i]].size(); j++)
| ~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0; i<lin.size(); i++)
| ~^~~~~~~~~~~
supertrees.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=0; i<cc.size(); i++)
| ~^~~~~~~~~~
supertrees.cpp:96:11: error: could not convert '(int (*)[n])(& ans)' from 'int (*)[n]' to 'std::vector<std::vector<int> >'
96 | build(ans);
| ^~~
| |
| int (*)[n]
