#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1005
struct UnionFind{
int parent[MAXN];
int siz[MAXN];
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void make_set(int v) {
parent[v] = v;
siz[v] = 1;
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] < siz[b])
swap(a, b);
parent[b] = a;
siz[a] += siz[b];
}
}
};
int n;
int grid[MAXN][MAXN];
UnionFind u1;
bool ans1 = true;
vector<int> vv[MAXN];
bool b[MAXN][MAXN];
bool solve(vector<int> ps){
if(ps.size() == 0) return;
int m = ps.size();
UnionFind uone;
for(auto i : ps) uone.make_set(i);
for(int i = 0; i<m; i++){
for(int j = 0; j<m; j++){
if(grid[ps[i]][ps[j]] == 1) uone.union_sets(ps[i], ps[j]);
}
}
for(int i = 0; i<m; i++){
for(int j = 0; j<m; j++){
if(grid[ps[i]][ps[j]] == 2 && uone.find_set(ps[i]) == uone.find_set(ps[j])){
return false;
}
}
}
vector<int> comps[MAXN];
for(int i = 0; i<m; i++) comps[uone.find_set(i)].push_back(i);
int num = 0;
vector<int> good;
for(int i = 0; i<MAXN; i++) if(comps[i].size() > 0) num++, good.push_back(i);
if(num == 2){
return false;
}
for(int i = 0; i<good.size(); i++){
for(int j = 0; j<comps[good[i]].size()-1; j++){
b[comps[good[i]][j]][comps[good[i]][j+1]] = 1;
b[comps[good[i]][j+1]][comps[good[i]][j]] = 1;
}
b[comps[good[i]][0]][comps[good[(i+1)%good.size()]][0]] = 1;
b[comps[good[(i+1)%good.size()]][0]][comps[good[i]][0]] = 1;
}
}
int calc(vector<vector<int>> p){
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("a.in", "r", stdin);
// cin >> n;
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++) grid[i][j] = p[i][j];
}
for(int i = 0; i<n; i++) u1.make_set(i);
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++) if(grid[i][j] != 0) u1.union_sets(i, j);
}
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(grid[i][j] == 0 && u1.find_set(i) == u1.find_set(j)){
return 0;
}
}
}
// cout << "hi" << endl;
for(int i = 0; i<n; i++){
vv[u1.find_set(i)].push_back(i);
}
// for(int i = 0; i<n; i++) cout << u1.find_set(i) << endl;
for(int i = 0; i<n; i++) solve(vv[i]);
vector<vector<int>> bb(n, vector<int>(n));
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++) bb[i][j] == b[i][j];
}
build(bb);
return 1;
}
int construct(vector<vector<int>> p){
n = p.size();
return calc(p);
}
Compilation message
supertrees.cpp: In function 'bool solve(std::vector<int>)':
supertrees.cpp:41:24: error: return-statement with no value, in function returning 'bool' [-fpermissive]
41 | if(ps.size() == 0) return;
| ^~~~~~
supertrees.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 0; i<good.size(); i++){
| ~^~~~~~~~~~~~
supertrees.cpp:66:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j = 0; j<comps[good[i]].size()-1; j++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int calc(std::vector<std::vector<int> >)':
supertrees.cpp:102:43: warning: value computed is not used [-Wunused-value]
102 | for(int j = 0; j<n; j++) bb[i][j] == b[i][j];
supertrees.cpp: In function 'bool solve(std::vector<int>)':
supertrees.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
73 | }
| ^
