//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include "supertrees.h" using namespace std; const int sz=1001,INF=1000000000; vector<int>parent(sz,-1),Parent(sz,-1); int get(int num) { if(parent[num]<0) { return num; } else { parent[num]=get(parent[num]); return get(parent[num]); } } void unite(int num1,int num2) { int res1=get(num1),res2=get(num2); if(res1!=res2) { if(parent[res1]>parent[res2]) { swap(res1,res2); } parent[res1]+=parent[res2],parent[res2]=res1; } } int Get(int num) { if(Parent[num]<0) { return num; } else { Parent[num]=Get(Parent[num]); return Get(Parent[num]); } } void Unite(int num1,int num2) { int res1=Get(num1),res2=Get(num2); if(res1!=res2) { if(Parent[res1]>Parent[res2]) { swap(res1,res2); } Parent[res1]+=Parent[res2],Parent[res2]=res1; } } int construct(vector<vector<int>>nums) { vector<vector<int>>ans(nums.size(),vector<int>(nums.size(),0)); for(int i=0;i<nums.size();i++) { for(int j=0;j<nums.size();j++) { if(nums[i][j]==2) { unite(i,j); } } } for(int i=0;i<nums.size();i++) { for(int j=0;j<nums.size();j++) { if(nums[i][j]==0) { if(get(i)==get(j)) { return 0; } } } } for(int i=0;i<nums.size();i++) { for(int j=i+1;j<nums.size();j++) { if(nums[i][j]==2) { Unite(i,j); } } } for(int i=0;i<nums.size();i++) { for(int j=i+1;j<nums.size();j++) { if(Get(i)==Get(j)) { ans[i][j]=1,ans[j][i]=1; } } } build(ans); return 1; }