#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
int boss[4][NMAX];
vector<int> dansComp[4][NMAX];
vector<int> chemins[4][NMAX];
int findBoss(int noeud, int iType)
{
if(boss[iType][noeud] == noeud) return noeud;
return boss[iType][noeud] = findBoss(boss[iType][noeud], iType);
}
int _size[4][NMAX];
bool merge(int a, int b, int iType)
{
a = findBoss(a, iType);
b = findBoss(b, iType);
if(a == b) return false;
if(_size[iType][b] > _size[iType][a])
{
swap(a, b);
}
_size[iType][a] += _size[iType][b];
boss[iType][b] = a;
for(int i : dansComp[iType][b]) dansComp[iType][a].push_back(i);
dansComp[iType][b].clear();
return true;
}
vector<vector<int>> answer;
void creer(int a, int b, int iType)
{
answer[a][b] = 1;
answer[b][a] = 1;
merge(a, b, iType);
}
/*
bool dansCycle[NMAX];
void parcours(int noeud)
{
for(int pro : chemins[1][noeud])
{
if(findBoss(pro) == findBoss(noeud)) continue;
creer(noeud, pro);
parcours(pro);
}
}/** */
int vu[NMAX];
int construct(vector<vector<int>> p) {
int n = p.size();
answer.resize(n, vector<int>(n));
for(int i = 0; i < n; i++)
{
for(int n = 0; n < 4; n++)
{
_size[n][i] = 1;
boss[n][i] = i;
dansComp[n][i].push_back(i);
}
for(int v = 0; v < n; v++) answer[i][v] = 0;
}
for(int i = 0; i < n; i++)
{
for(int c = 0; c < n ; c ++)
{
if(i == c) continue;
int type = p[i][c];
chemins[type][i].push_back(c);
}
}
/*
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < i; autre++)
{
if(p[i][autre] == 1)
{
creer(findBoss(i), findBoss(autre));
}
}
}
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < i; autre++)
{
if(p[i][autre] == 0)
{
if(findBoss(i) == findBoss(autre)) return 0;
}
}
}
/** */
//type1
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(p[i][autre] != p[autre][i]) return 0;
if(i == autre) continue;
if(p[i][autre] == 1)
{
merge(findBoss(i, 1), findBoss(autre, 1), 1);
}
}
}
for(int noeud1 = 0; noeud1 < n; noeud1++)
{
if(findBoss(noeud1, 1) != noeud1) continue;
if(dansComp[1][noeud1].size() == 1) continue;
for(int autre : dansComp[1][noeud1])
{
if(autre == noeud1) continue;
creer(noeud1, autre, 1);
}
}
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(i == autre) continue;
if((findBoss(i, 1) == findBoss(autre, 1)) && (p[i][autre] != 1)) return 0;//Averifier
}
}
//type2
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(i == autre) continue;
if(p[i][autre] == 2)
{
merge(findBoss(i, 2), findBoss(autre, 2), 2);
}
}
}
for(int noeud2 = 0; noeud2 < n; noeud2++)
{
if(findBoss(noeud2, 2) != noeud2) continue;
if(dansComp[2][noeud2].size() == 1) continue;
if(dansComp[2][noeud2].size() == 2) return 0;
int b = dansComp[2][noeud2][dansComp[2][noeud2].size()-1];
b = findBoss(b, 1);
vu[b] = 2;
int nbApp = 0;
for(int iDansComp=0; iDansComp < dansComp[2][noeud2].size(); iDansComp++)
{
int a = dansComp[2][noeud2][iDansComp];
a= findBoss(a, 1);
if((vu[a] == 2) && (iDansComp != dansComp[2][noeud2].size()-1))
continue;
vu[a] = 2;
nbApp++;
creer(a, b, 2);
b = a;
}
if(nbApp < 2) return 0;
}
/*
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(i == autre) continue;
if((findBoss(i, 2) == findBoss(autre, 2)) && (p[i][autre] != 2)) return 0;
}
}
/** */
// cout << "passe" << endl;
/**
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
//cout << i << " " << autre << endl;
if(i == autre) continue;
if(p[i][autre] == 0)
{
if(findBoss(i) == findBoss(autre)) return 0;
}
}
}
//cout << "passe" << endl;
/** */
/*
// cycle de 2
for(int i = 0; i < n; i++)
{
if(findBoss(i) == i)
{
if(dansComp[i].size() == 1) continue;
//if(dansComp[i].size() == 2) return 0;
// cout << endl;
for(int iDansComp=0; iDansComp < dansComp[i].size(); iDansComp++)
{
//cout << dansComp[i][iDansComp] << " ";
int b;
if(iDansComp == 0)
{
b = dansComp[i][dansComp[i].size()-1];
}
else
b = dansComp[i][iDansComp-1];
int a = dansComp[i][iDansComp];
dansCycle[a] = true;
creer(a, b);
}
}
}
// parcours pour arbre depuis cycle
for(int i = 0; i < n; i++)
{
if(!dansCycle[i]) continue;
parcours(i);
}
//reste
for(int i = 0; i < n; i++) parcours(i);
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(i == autre) continue;
if(((p[i][autre] == 0) && (findBoss(i) == findBoss(autre))) || ((p[i][autre] > 0) && (findBoss(i) != findBoss(autre)))) return 0;
}
}
/** */
build(answer);
return 1;
}
