#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct UF {
vi p, rnk;
int nsets;
UF(int n) {
p = vi(n);
for (int i = 0; i < n; ++i)p[i] = i;
rnk = vi(n);
nsets = n;
}
int parent(int i) {
if (p[i] == i)return i;
return p[i] = parent(p[i]);
}
bool check(int a, int b) {
return parent(a) == parent(b);
}
void join(int a, int b) {
if (check(a,b))return;
nsets--;
a = parent(a);
b = parent(b);
if (rnk[a] > rnk[b]) {
p[b] = a;
} else {
p[b] = a;
if (rnk[a] == rnk[b]) {
rnk[b]++;
}
}
}
};
int construct2(vector<vi> p) {
int n = p.size();
UF uf(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j)continue;
if (p[i][j] == 2) {
uf.join(i,j);
} else {
if (uf.check(i,j))return 0;
}
}
}
vector<vi> ring(n);
for (int i = 0; i < n; ++i) {
ring[uf.parent(i)].push_back(i);
}
vector<vi> ans(n, vi(n, 0));
for (auto vv : ring) {
if (vv.size() <= 1)continue;
if (vv.size() == 2)return 0;
for (int i = 0; i < vv.size(); ++i) {
int pp = (i == 0 ? vv.back() : vv[i-1]);
ans[v[i]][pp] = 1;
ans[pp][v[i]] = 1;
}
}
build(ans);
return 1;
}
int construct(vector<vi> p) {
int n = p.size();
for (auto vv : p) {
for (auto x : vv) {
if (x == 2)return construct2(p);
}
}
UF uf(n);
vector<vi> ans(n, vi(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j)continue;
if (p[i][j]) {
uf.join(i,j);
} else {
if (uf.check(i,j))return 0;
}
}
}
for (int i = 0; i < n; ++i) {
int par = uf.parent(i);
if (par == i)continue;
ans[i][par] = 1;
ans[par][i] = 1;
}
build(ans);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct2(std::vector<std::vector<int> >)':
supertrees.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < vv.size(); ++i) {
| ~~^~~~~~~~~~~
supertrees.cpp:74:17: error: 'v' was not declared in this scope
74 | ans[v[i]][pp] = 1;
| ^
