Codeforces 1142E（图、交互）

题目传送

官方题解说的很好了，剩下的就是读大佬代码了，前面是tarjan求SCC缩点图。我图论没学过，接下来删点是怎么操作看得有点头秃，直到我看到了%%%安德鲁何神仙的代码。
按照题面连通紫线以后，我们姑且先考虑从入度为0的点着手看看是否可行。由于都是入度为0的点，所以现在我们连的都是绿边。
假如连了\[a\rightarrow b\]这条边，而又有\[b\rightarrow c\]这条紫边，那显然是要断开的，然后c如果入度为0，它也成为了一个候选。
这种做法会不会导致一开始a连向b的，然后我们把b删了，而a其实又不是最后答案、反而b是可行的呢？

无碍，当b最后可行时，意味着b会通过别的节点和绿边走到a，而a到b又有绿边，也就是这是个绿环，要么环内任意点为答案，要么外部点为答案，走通到环内，是肯定有答案的，所以删了b无碍。

这个做法就不需要SCC了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

const int maxn = 1e5 + 5;
int n, m, used[maxn], indeg[maxn];
vector<int> adj[maxn];
queue<int> Q;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }

    function<void(int)> dfs = [&](int cur) {
        if (used[cur])  return;
        used[cur] = 1;
        vector<int> tmp;
        for (int son : adj[cur]) {
            if (used[son] == 1) continue;
            dfs(son);
            tmp.push_back(son);
            indeg[son]++;
        }
        used[cur] = 2;
        adj[cur] = tmp;
    };

    for (int i = 1; i <= n; i++)    dfs(i);

    for (int i = 1; i <= n; i++) {
        if (!indeg[i]) {
            Q.push(i);
        }
    }

    while (Q.size() >= 2) {
        int a = Q.front(); Q.pop();
        int b = Q.front(); Q.pop();

        cout << "? " << a << ' ' << b << '\n' << flush;
        int answer; cin >> answer;

        if (!answer)    swap(a, b);
        for (int i : adj[b]) {
            if (!--indeg[i]) {
                Q.push(i);
            }
        }
        Q.push(a);
    }

    cout << "! " << Q.front() << endl;
    return 0;
}

Codeforces 1142E（图、交互）

原文：https://www.cnblogs.com/AlphaWA/p/10667859.html