2392.build a matrix with condition
給兩個二維陣列rowconditions, colconditions和一常數k,其中rowcondition陣列
每一項[a,b]代表a會在b的上方列中，例如b在i-th row,a就一定只能在0-i-1 th row中，
colconditions類似，[a,b]代表a一定在b的左邊col中，給定1-k的數字回傳
k*k合乎規定的matrix,如果條件出現矛盾則回傳empty matrix.
思路:把rowconditions colconditions當成兩個描述不同有向圖的edge list
轉成圖後做topological sort，如果有cycle形成則回傳empty，再依兩個不同圖的
topological sort結果先後填回矩陣中。
public:
void topoutill(int v,vector<bool>& visted, vector<vector<int>>&
adv,stack<int>&rec){
visted[v]=true;
for(auto k:adv[v]){
if(!visted[k]){
topoutill(k,visted,adv,rec);
}
}
rec.push(v);
}
vector<int> toposort(vector<vector<int>>& adv, int c){
//c=k+1, so start from 1
//note ans[0] is for 1;
stack<int> record;
unordered_map<int,int> pos;
vector<int> ans;
int idx=0;
vector<bool> vied(c,false);
for(int i=1;i<c;i++){
if(!vied[i]){
topoutill(i,vied,adv,record);
}
}
while(!record.empty()){
pos[record.top()]=idx;
ans.push_back(record.top());
record.pop();
idx+=1;
}
for(int j=1;j<c;j++){
for(auto p: adv[j]){
if (pos[j]>pos[p]){
return {};
}
}
}
return ans;
}
vector<vector<int>> buildMatrix(int k, vector<vector<int>>&
rowConditions, vector<vector<int>>& colConditions) {
vector<vector<int>> adj_row(k+1);
vector<vector<int>> adj_col(k+1);
for(auto g: rowConditions){
adj_row[g[0]].push_back(g[1]);
}
for(auto g: colConditions){
adj_col[g[0]].push_back(g[1]);
}
vector<int> row_sort=toposort(adj_row,k+1);
vector<int> col_sort=toposort(adj_col,k+1);
if(row_sort.empty() || col_sort.empty()){
return {};
}
vector<vector<int>> ans(k,vector<int>(k,0));
unordered_map<int,int> loc_by_row;
for(int i=0;i<k;i++){
ans[i][0]=row_sort[i];
loc_by_row[row_sort[i]]=i;
}
for(int i=0;i<k;i++){
int ll=loc_by_row[col_sort[i]];
ans[ll][0]=0;
ans[ll][i]=col_sort[i];
}
return ans;
}