/*
idea for subtask 4:
- separate the nodes into different components according to input
- in each component, find the nodes that require exactly one path
from that node to some other node in the component
- create a tree using these nodes
- assign one node "root" node and create a cycle with all the 2-path
nodes and this node
*/
#include "supertrees.h"
#include <vector>
#include <map>
#include <iostream>
#include <set>
using namespace std;
#define sz(x) (int)x.size()
struct DSU {
int n;
vector<int> link, size;
DSU(int sz) {
n = sz;
link.resize(sz);
size.resize(sz);
for (int i = 0; i < n; i++) {
link[i] = i;
size[i] = 1;
}
}
int find(int x) {
while (x != link[x])
x = link[x];
return x;
}
bool same(int a, int b) {
return find(a) == find(b);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return;
if (size[a] < size[b])
swap(a, b);
link[b] = a;
size[a] += size[b];
}
};
int construct(std::vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n));
DSU d(n+1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (p[i][j]) {
d.unite(i, j);
}
}
}
vector<vector<int>> component;
vector<bool> done(n);
for (int i = 0; i < n; i++) {
if (done[i])
continue;
int l = d.find(i);
vector<int> temp;
for (int j = 0; j < n; j++) {
if (d.find(j) == l) {
done[j] = true;
temp.push_back(j);
}
}
if (temp.size() > 1)
component.push_back(temp);
}
for (auto c : component) {
if (sz(c) <= 1)
continue;
DSU dsu(n+1);
vector<int> two;
set<int> roots;
for (int i = 0; i < sz(c); i++) {
int r = c[i];
bool o = false;
for (int j = 0; j < n; j++) {
if (j == r)
continue;
if (p[r][j] == 1) {
o = true;
if (dsu.same(r, j))
continue;
dsu.unite(r, j);
answer[r][j] = 1;
answer[j][r] = 1;
roots.insert(dsu.find(r));
}
}
if (!o)
two.push_back(r);
}
if (!two.empty()) {
for (auto r : roots)
two.push_back(r);
for (int i = 0; i < sz(two)-1;i++) {
answer[two[i]][two[i+1]] = 1;
answer[two[i+1]][two[i]] = 1;
}
answer[two.back()][two[0]] = 1;
answer[two[0]][two.back()] = 1;
}
}
for (int i = 0; i < n; i++) {
answer[i][i] = 0;
}
build(answer);
return 1;
}
