CROC 2016 - Elimination Round (Rated Unofficial Edition) D. Robot Rapping Results Report 拓扑排序+二分...

题目链接：

http://www.codeforces.com/contest/655/problem/D

题意：

题目是要求前k个场次就能确定唯一的拓扑序，求满足条件的最小k。

题解：

二分k的取值，做拓扑排序的时候只要每次只有一个元素没有前驱就可以唯一了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
const int maxn = 101010;
int n, m;
struct Edge {
int v, ne;
Edge(int v, int ne) :v(v), ne(ne) {}
Edge() {}
}egs[maxn*2];
int head[maxn], tot;
void addEdge(int u, int v) {
egs[tot] = Edge(v, head[u]);
head[u] = tot++;
}
int ind[maxn];
bool ok(int m) {
memset(ind, 0, sizeof(ind));
for (int i = 0; i <= m; i++) {
ind[egs[i].v]++;
}
queue<int> Q;
for (int i = 0; i < n; i++) {
if (ind[i] == 0) {
Q.push(i);
}
}
while (!Q.empty()) {
if (Q.size() > 1) return false;
int u = Q.front(); Q.pop();
int p = head[u];
while (p != -1) {
Edge& e = egs[p];
if (p <= m) {
ind[e.v]--;
if (ind[e.v] == 0) {
Q.push(e.v);
}
}
p = e.ne;
}
}
return true;
}
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
init();
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v); u--, v--;
addEdge(u, v);
}
int l = -1, r = tot-1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (!ok(mid)) l = mid;
else r = mid;
}
//printf("l:%dn", l);
if (!ok(r)) printf("-1n");
else printf("%dn", r + 1);
}
return 0;
}