（未更新完，做到相关题再更新相关部分

无向图判断有无环并输出环上点

利用变种拓扑排序，先把度为1的点存入队中，每次取出队头，遍历邻接点，再将该条边删除也就是将邻接点度数减一，直至队空，然后所有度数不为0的点都是在环上的点，输出即可

code

for (int i = 0; i < n; i ++ )
{
    int x, y;
    cin >> x >> y;
    add(x, y), add(y, x);

    ind[x] ++, ind[y] ++ ;
}
    
function<void()> topsort = [&]()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (ind[i] == 1) q.push(i);

    while (q.size())
    {
        int u = q.front();
        q.pop();

        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if (-- ind[v] == 1) q.push(v);
        }
    }
};

topsort();

for (int i = 1; i <= n; i ++ )
	if (ind[i] > 1) ans = true;

有向图判断有无环并输出环上点

拓扑排序 是目前来看的一种最优方式，即把所有入度为 0 的点存进队列，每次取出队头，遍历其邻接点，并将邻接点的入度减 1，若入度在减 1 后变为 0，则存入队列。以此类推，直到队列中没有元素，此时入度不为 0 的点在环上

code

for (int i = 0; i < n; i ++ )
{
    int x, y;
    cin >> x >> y;
    add(x, y);

    ind[y] ++ ;
}
    
function<void()> topsort = [&]()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (ind[i] == 0) q.push(i);

    while (q.size())
    {
        int u = q.front();
        q.pop();

        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if (-- ind[v] == 0) q.push(v);
        }
    }
};

topsort();

for (int i = 1; i <= n; i ++ )
	if (ind[i] > 0) ans = true;

有向图找最小/大环

利用并查集，每加一条边，判断当前这两个端点是否连通，如果不连通就更新他们的长度和父结点情况，如果这两个端点已经连通，那么加上这一条边一定能使得形成一个环，环的长度就是两个端点距离祖先结点的和再加一

code

int find(int x)
{
    if (x != fa[x])
    {
        int last = fa[x];
        fa[x] = find(fa[x]);
        dist[x] += dist[last];
    }
    return fa[x];
}

void func(int a, int b)
{
    int aa = find(a), bb = find(b);

    if (aa == bb) ans = min(ans, dist[a] + dist[b] + 1);
    else
    {
        fa[a] = bb;
        dist[a] = dist[b] + 1;
    }
}

ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
    int x;
    cin >> x;
    func(i, x);
}

有向图找到所有环

也就是找到有向图的强连通分量，利用tarjan算法

code

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp; // 先将dfn和low都初始化为时间戳
    stk.push(u), in_stk[u] = true; // u加入栈中

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i]; // 取出u的所有邻点j
        if (!dfn[j]) // 如果j还没被遍历
        {
            tarjan(j);
            low[u] = min(low[u], low[j]); // 用low[j]更新low[u]
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]); // 如果j已入栈 则用dfn[j]更新low[u]
    }

    if (dfn[u] == low[u]) // 如果该点是所在强连通分量的最高点
    {
        ++ scc_cnt; // 强连通分量数量加一
        int y;
        do {
            y = stk.top(); // 取出栈顶元素
            stk.pop();
            in_stk[y] = false;

            id[y] = scc_cnt; // 标记每个点所在的连通分量编号
        } while (y != u); // 直到取到此连通分量的最高点为止
    }
}

缩点code

for (int i = 1; i <= n; i ++ )
    for (int j = h[i]; ~j; j = ne[j])
    {
        int k = e[j]; // 遍历i的所有邻点k
        int a = id[i], b = id[k]; // 记录ik所在连通分量编号
        if (a != b) dout[a] ++ ; // 如果ik不在同一个连通分量 就在两个连通分量之间连一条i指向k的边
    }