AOJ 0519 : Worst Sportswriter
問題リンク:Worst Sportswriter | Aizu Online Judge
解法:
トポロジカル順で色を塗っていき同じ色を持つノードが複数存在するかどうかをしらべた
同じ色を持つノードが複数存在する => どちらが先でも良い
ノード数をnとする
色は0からn-1までの整数
color[i] := ノードiの色
最初colorの全ての要素は0で初期化する
for i 0..n-1 for j 0..(トポロジカル順でのノードiの出次数) color[トポロジカル順でのノードiからいけるノードのj番目] = max(itself, color[トポロジカル順でのノードi] + 1 );
みたいな感じで色を塗っていった
コード----------------------
struct P { int to,cost; P(int to=inf,int cost=inf):to(to),cost(cost){} }; //topologicalSort int n,m,a,b; int main() { cin >> n >> m; assert(n >= 2); vector<vector<P> > G(n,vector<P>()); rep(_,m) { scanf("%d %d",&a,&b); a--,b--; G[a].push_back(P(b,1)); } vector<int> order; topologicalSort(G,order); rep(i,order.size())cout << order[i]+1 << endl; int color[n],cnt[n]; rep(i,n)color[i] = 0,cnt[i] = 0; rep(i,n)rep(j,G[order[i]].size()) color[G[order[i]][j].to] = max(color[G[order[i]][j].to],color[order[i]]+1); rep(i,n)cnt[color[i]]++; bool check = false; rep(i,n)if(cnt[i] >= 2)check = true; cout << check << endl; return 0; }