LeetCode Weekly Contest 155 : 1203. Sort Items by Groups Respecting Dependencies

今回は不参加でした。
https://leetcode.com/contest/weekly-contest-155/problems/sort-items-by-groups-respecting-dependencies/

問題

N個のアイテムがあり、それぞれM個のグループのいずれか1つに属しているか、もしくは何にも属していない。
これらのアイテムを順に並べる。
その際、各アイテムに対し、その手前になければならないアイテムが指定される。
また、同じグループに属するものは連続していなければならない。

条件を満たす並び順を求めよ。

解法

まず「何にも属していない」アイテムは、新規グループを作り単独でグループを成すとみなそう。
前後関係の条件が、グループ間かグループ内かで分けておく。
あとはよくあるトポロジカルソートである。
まずグループ間をトポロジカルソート順で並べることとし、グループ内も同様にトポロジカルソート順で並べればよい。

vector<int> G[60606];
vector<int> GE[60606];
int inG[60606];
vector<int> VE[60606];
int inV[60606];

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
		FORR(g,group) if(g==-1) g=m++;
        int i;
        ZERO(inG);
        ZERO(inV);
        FOR(i,60600) G[i].clear(), GE[i].clear(), VE[i].clear();
        FOR(i,n) G[group[i]].push_back(i);
        FOR(i,n) {
			FORR(b,beforeItems[i]) {
				if(group[i]==group[b]) {
					VE[b].push_back(i);
					inV[i]++;
				}
				else {
					GE[group[b]].push_back(group[i]);
					inG[group[i]]++;
				}
			}
		}
		queue<int> Q;
		vector<int> R;
		FOR(i,m) if(inG[i]==0) Q.push(i);
		
		while(Q.size()) {
			int g=Q.front();
			Q.pop();
			
			queue<int> Q2;
			FORR(v,G[g]) if(inV[v]==0) Q2.push(v);
			int lef=G[g].size();
			while(Q2.size()) {
				int v=Q2.front();
				Q2.pop();
				lef--;
				R.push_back(v);
				FORR(v2,VE[v]) {
					inV[v2]--;
					if(inV[v2]==0) Q2.push(v2);
				}
			}
			if(lef) return {};
			
			FORR(e,GE[g]) {
				inG[e]--;
				if(inG[e]==0) Q.push(e);
			}
		}
		
		if(R.size()!=n) return {};
		return R;
		
    }
};

まとめ

8pt久しぶりかも。