https://ac.nowcoder.com/acm/contest/330/F

C++版本一

题解：

std

图论，二分，拓扑排序

题意是想让大家判断有向图是否存在环。判断有向图是否有环可以使用拓扑排序。
但是不能每次加边的时候就进行判断。
由于不存在撤销操作，所以可以发现答案一定是一连串的Yes后再有一连串的No。
只需要二分最后一个Yes的位置，用拓扑排序/DFS判环即可。

#include <bits/stdc++.h>
using namespace std;
 
bool ok(int x, int n, const vector<pair<int, int>>& edges)
{
    vector<vector<int>> G(n);
    vector<int> deg(n);
    for (int i = 0; i < x; i++)
    {
        G[edges[i].first].push_back(edges[i].second);
        ++deg[edges[i].second];
    }
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (!deg[i]) q.push(i);
    int tot = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        ++tot;
        for (auto& v : G[u])
            if (--deg[v] == 0) q.push(v);
    }
    return tot == n;
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<pair<int, int>> edges;
    for (int i = 0, u, v; i < m; i++)
    {
        scanf("%d%d", &u, &v);
        --u, --v;
        edges.emplace_back(u, v);
    }
    int l = 1, r = m, ans;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (ok(mid, n, edges))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    for (int i = 0; i < ans; i++) puts("Yes");
    for (int i = ans; i < m; i++) puts("No");
}