CFR 645 D. Robot Rapping Results Report ( Graph, TopoSort, Binary Search )

Problem - 645D - Codeforces

題意：
有 N 個機器人打鬥，機器人之間勝負是依戰鬥力的大小關係定的，而所有機器人的戰鬥力相異。依順序給機器人編號 u[ i ], v[ i ]，表示編號 u[ i ] 的機器人戰鬥力比 v[ i ] 的機器人高。求第幾個資訊開始能確定所有機器人的戰鬥力大小關係。若無法則輸出 -1。

資料規模：
1 ≤ N ≤ 1e5
1 ≤ M ≤ 1e5

解法：
對答案二分搜。進行拓撲排序後，若且唯若所有相鄰的機器人都有資訊表示強弱關係，才能確定所有機器人之間的戰鬥力大小。

時間 / 空間複雜度：
O( N lg M ) / O( N )

const int MOD7 = ( int ) 1e9 + 7;

int N, M;
vp edge;

void init(){
  cin >> N >> M;
  edge = vp( M );
  for( int i = 0; i < M; ++i ){
    int u, v; cin >> u >> v; --u, --v;
    edge[ i ] = make_pair( u, v );
  }
}

void topo_sort( int u, const vvi &g, vi &sorted, vi &vis ){
  for( int v : g[ u ] ){
    if( vis[ v ] ) continue;
    vis[ v ] = 1;
    topo_sort( v, g, sorted, vis );
  }
  sorted.emplace_back( u );
}

int ok( int x ){
  unordered_set< ll > has_edge;
  vvi g( N );
  for( int i = 0; i < x; ++i ){
    has_edge.emplace( 1LL * MOD7 * edge[ i ].first + edge[ i ].second );
    g[ edge[ i ].first ].emplace_back( edge[ i ].second );
  }
  vi sorted;
  vi vis( N );
  for( int i = 0; i < N; ++i ){
    if( vis[ i ] ) continue;
    vis[ i ] = 1;
    topo_sort( i, g, sorted, vis );
  }
  for( int i = 0; i + 1 < sorted.size(); ++i ){
    if( not has_edge.count( 1LL * MOD7 * sorted[ i + 1 ] + sorted[ i ] ) ){
      return 0;
    }
  }
  return 1;
}

void preprocess(){
  int ans = -1;
  for( int lb = 1, rb = M; lb <= rb; ){
    int mid = lb + rb >> 1;
    if( ok( mid ) ){
      ans = mid;
      rb = mid - 1;
    } else{
      lb = mid + 1;
    }
  }
  cout << ans << endl;
}