#include "supertrees.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
vector<int> parent, Size;
vector<pii> zero, two;
vector<int>nodes;
int findUpar(int node){
if(node == parent[node]) return node;
return parent[node] = findUpar(parent[node]);
}
void Union(int u, int v){
int pu = findUpar(u), pv = findUpar(v);
if(pu == pv) return ;
if(Size[pu] > Size[pv]){
parent[pv] = pu; Size[pu] += Size[pv];
}else{
parent[pu] = pv; Size[pv] += Size[pu];
}
}
bool cycle(int sr, vector<int>Adj[], vector<bool>&visited, int n){
visited[sr] = true;
queue<pii>q; //{node, par}
q.push({sr, -1});
while(!q.empty()){
int node = q.front().first;
int par = q.front().second;
q.pop();
for(int adjNode: Adj[node]){
if(!visited[adjNode]){
visited[adjNode] = true;
q.push({adjNode, node});
}else if(par != adjNode){
return true;
}
}
}
return false;
}
int construct(vector<vector<int>>p){
int n = p.size(); parent.resize(n); Size.resize(n);
for(int i = 0; i<n; i++) parent[i] = i, Size[i] = 1;
vector<vector<int>>adj(n, vector<int>(n, 0));
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(p[i][j] == 0){
zero.push_back({i, j}); /// i and j must not be in the same compo
}else if(p[i][j] == 1){
Union(i, j);
}else if(p[i][j] == 2){
two.push_back({i, j});
}else if(p[i][j] == 3){
return 0;
}
}
}
///mark 1
for(int i = 0; i<n; i++){
int pi = findUpar(i);
if(pi != i){
adj[i][pi] = 1; adj[pi][i] = 1;
}
}
vector<int> Adj[n];
///mark 2
for(pair<int,int> it: two){
int u = it.first, v = it.second;
int pu = findUpar(u), pv = findUpar(v);
if(pu == pv) return 0;
adj[pu][pv] = 1; adj[pv][pu] = 1;
Adj[pu].push_back(pv);
Adj[pv].push_back(pu);
}
///2-> check cycle
vector<bool>visited(n, false);
int cnt = 0;
for(int i = 0; i<n; i++){
if(!visited[i]){
bool Cycle = cycle(i, Adj, visited, n);
if(Cycle) cnt++;
}
}
if(cnt != 1){
return 0;
}
///Union 2
for(pii it: two){
Union(it.first, it.second);
}
///Check zero
for(pii it: zero){
int u = it.first, v = it.second;
int pu = findUpar(u), pv = findUpar(v);
if(pu == pv) return 0;
}
build(adj);
return 1;
}
