#include "supertrees.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
const int N = 2000;
bool vu[N];
bool fini[N];
int composante[N], iArbre[N];
int construct(vector<vector<int>> nChemins) {
int nNoeuds = sz(nChemins), nCCs = 0;
vector<vector<int>> aretes(nNoeuds);
for (vector<int>& ligne : aretes){
ligne.resize(nNoeuds);
for (int& val : ligne)
val = 0;
}
for (int root = 0; root < nNoeuds; ++root){
if (vu[root]) continue;
vector<int> cc;
for (int noeud = 0; noeud < nNoeuds; ++noeud){
if (root == noeud || nChemins[noeud][root] > 0){
cc.pb(noeud);
composante[noeud] = nCCs;
}
}
vector<int> darons;
int nArbres = 0;
for (int noeud : cc){
if (fini[noeud]) continue;
darons.pb(noeud);
for (int autreNoeud : cc){
if (!fini[autreNoeud] && nChemins[autreNoeud][noeud] == 1){
fini[autreNoeud] = true;
iArbre[autreNoeud] = nArbres;
if (autreNoeud != noeud)
aretes[noeud][autreNoeud] = aretes[autreNoeud][noeud] = 1;
}
}
nArbres++;
}
if (sz(darons) > 1){
for (int i = 0; i < sz(darons); ++i){
int a = darons[i], b = darons[(i + 1)%sz(darons)];
aretes[a][b] = aretes[b][a] = 1;
}
}
if (sz(darons) == 2)
return 0;
nCCs++;
}
//verifier que c'est bon
bool ok = true;
for (int noeud = 0; noeud < nNoeuds; ++noeud)
for (int voisin = 0; voisin < nNoeuds; ++voisin){
if (composante[noeud] != composante[voisin])
ok &= (nChemins[noeud][voisin] == 0);
else if (iArbre[noeud] == iArbre[voisin])
ok &= (nChemins[noeud][voisin] == 1);
else
ok &= (nChemins[noeud][voisin] == 2);
}
if (!ok)
return 0;
build(aretes);
return 1;
}
