graph/scc_tounament_by_indegrees.hpp

• View this file on GitHub
• Last update: 2023-03-15 22:02:24+09:00
• Include: #include "graph/scc_tounament_by_indegrees.hpp"

Verified with

• test/mytest/scc_tournament.test.cpp

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