#include "supertrees.h" #include <vector> #include <set> using namespace std; int construct(vector< vector<int> > p) { int n = p.size(); vector< vector<int> > b(n); for(int i = 0; i < n; i++) b[i] = vector<int>(n, 0); vector<int> group(n, -1); set<int> grouplist; for(int i = 0; i < n; i++) { group[i] = i; grouplist.clear(); for(int j = 0; j < i; j++) if(p[i][j]) grouplist.insert(group[j]); for(int j = 0; j < i; j++) if(grouplist.find(group[j]) != grouplist.end()) group[j] = i; } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(group[i] == group[j] && p[i][j] == 0) return 0; if(group[i] != group[j] && p[i][j] == 1) return 0; } } for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { if(p[i][j]) { b[i][j] = b[j][i] = 1; break; } } } for(int i = 0; i < n; i++) { int A, B; for(A = 0; A < n; A++) if(group[A] == i) break; if(A >= n) continue; for(B = n-1; B > A; B--) if(group[B] == i) break; if(B <= A) continue; b[A][B] = b[B][A] = 1; } build(b); return 1; }