読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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;
}