AtCoder Beginner Contest 285 D - Change Usernames（拓扑排序）

这题想到可以用map容器将string与一个端点下标对应，再建一个有向图，将问题转换成判断一个有向图是否有环

赛后补题网上搜如何判断图是否有环，学到了拓扑排序

拓扑排序是什么

图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

• 每个顶点出现且只出现一次。
• 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法：

1. 从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。

于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。

通常，一个有向无环图可以有一个或多个拓扑排序序列。这是因为可能同时存在多个入度为0的结点，这时，先处理哪个都是可以的。

整段引用了这篇博客

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
vector<int> e[N];
map<string, int> mp;
int ind[N], cnt, t;
queue<int> q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        string a, b;
        cin >> a >> b;
        if (mp.find(a) == mp.end()) mp[a] = ++ cnt;
        if (mp.find(b) == mp.end()) mp[b] = ++ cnt;
        e[mp[a]].push_back(mp[b]);
        ind[mp[b]] ++;
    }

    for (int i = 1; i <= cnt; i ++ )
        if (!ind[i]) q.push(i), t ++;

    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (auto &v : e[u])
        {
            ind[v] -= 1;
            if (!ind[v])
            {
                q.push(v);
                t ++;
            }
        }
    }

    if (t == cnt) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}