library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:heavy_check_mark: graph/scc_tounament_by_indegrees.hpp

Verified with

Code

pair<int, vc<int>> scc_tournament_by_indegrees(vc<int> indeg) {
  int N = len(indeg);
  auto I = argsort(indeg);
  vc<int> ANS(N);
  ll sm = 0;
  int nxt = 0;
  FOR(i, N) {
    int v = I[i];
    ANS[v] = nxt;
    // I[0:i] がひとつの成分かどうか
    sm += indeg[v];
    ll TS = sm - (i + 1) * i / 2;
    if (TS == 0) ++nxt;
  }
  return {nxt, ANS};
}
#line 1 "graph/scc_tounament_by_indegrees.hpp"
pair<int, vc<int>> scc_tournament_by_indegrees(vc<int> indeg) {
  int N = len(indeg);
  auto I = argsort(indeg);
  vc<int> ANS(N);
  ll sm = 0;
  int nxt = 0;
  FOR(i, N) {
    int v = I[i];
    ANS[v] = nxt;
    // I[0:i] がひとつの成分かどうか
    sm += indeg[v];
    ll TS = sm - (i + 1) * i / 2;
    if (TS == 0) ++nxt;
  }
  return {nxt, ANS};
}
Back to top page