题面描述:

给定一组元素及其依赖关系，其中一个元素可以依赖多个其他元素，且一个元素也可以被多个其他元素所依赖。在输入中，首先给出依赖关系的数量，接着每行描述一个元素及其依赖的元素。任务是输出唯一存在的循环依赖，从最小的元素编号开始，依次输出依赖关系，最后以该最小元素结束。通过分析依赖关系，可以确定循环依赖的路径。

思路

简化题意：给出若干条边组成的有向图，找出其中唯一的环，保证环一定存在。 直接 dfs ，遍历完点 u 还未找到环，则说明点 u 不在这个环上。 当某个点已经被遍历过一次，且在 dfs 过程中再次被遍历过，说明遍历完了一整个环。 具体实现上使用一个栈来存储 dfs 过程中遍历到的点，如果一个点 u 被遍历到了两次，则说明找到了这个环，且 u 是这个环上的点。 只需要依次弹出栈中的点，直至弹出 u 为止，这就是环中所有的点。 需要注意的是：

• 弹出栈中的点获得的是一个倒序的环，需要反转一下
• 如果一个点在遍历完毕后仍然未结束，说明这个点不在环上，需要从栈中弹出

时间复杂度：O(m), m 为所有的边的数量

题解

题目要求在给定的有向图中寻找唯一的环。我们可以通过深度优先搜索（DFS）的方法来实现这个目标。具体的步骤如下：

1. 数据结构：

   • 使用邻接表存储图的边，h 表示每个节点的邻接边的头部，e 表示边的目标节点，nxt 用于存储每条边的下一条边的索引。
   • vis 数组用于标记每个节点是否已经被访问。
   • onpath 数组用于标记当前 DFS 路径上的节点，以帮助识别环的存在。
   • path 数组用于记录当前 DFS 路径上的节点顺序。
   • cyc 数组用于存储找到的环，nc 记录环中节点的数量。

2. DFS 遍历：

   • 在 DFS 中，首先检查当前节点是否在 onpath 中。如果是，则说明找到了一个环，并记录环的路径。
   • 如果当前节点已经被访问过（即在 vis 中标记为 1），则直接返回，避免重复搜索。
   • 将当前节点添加到路径中，继续 DFS 遍历其所有邻接节点。

3. 环的输出：

   • 找到环后，从栈中弹出节点并记录，直到再次弹出起始节点，形成环。
   • 由于弹出的顺序是倒序的，因此需要在输出之前对环进行反转。
   • 最后输出环中的节点，并以最小的节点作为结尾。

4. 复杂度：

   • 整个算法的时间复杂度为 O(m)，其中 m 为图中的边数。

AC代码

• java

import java.util.*;

public class Main {
    static final int N = 100010; // 定义常量，最多支持的节点数
    static int n, cnt = 0, nc = 0; // n为边的数量，cnt用于边的计数，nc用于环中节点数量
    static int[] cyc = new int[N], path = new int[N], vis = new int[N], onpath = new int[N]; // cyc存储环，path存储当前路径，vis标记访问，onpath标记当前路径
    static int[] h = new int[N], e = new int[N << 1], nxt = new int[N << 1]; // h为邻接表头，e为边的目标，nxt为下一条边的索引
    static int cntv = 0; // 计数节点的数量
    static int[] vert = new int[N]; // 存储节点编号

    // 添加边的函数
    static void add(int u, int v) {
        nxt[cnt] = h[u]; // 将当前边的下一条边指向当前头部
        e[cnt] = v;      // 将边的目标设置为v
        h[u] = cnt++;    // 更新头部并计数
    }

    // 深度优先搜索函数
    static void dfs(int u, int idx) {
        if (onpath[u] == 1) { // 如果当前节点在路径上，说明找到了环
            int i = idx - 1;
            // 从路径中弹出节点，直到弹出u
            while (path[i] != u) {
                cyc[nc++] = path[i--];
            }
            cyc[nc++] = u; // 将u加入环中
            return;
        }
        if (vis[u] == 1) return; // 如果已经访问过，直接返回
        vis[u] = 1; // 标记节点为已访问
        onpath[u] = 1; // 标记节点为当前路径上的节点
        path[idx] = u; // 将当前节点记录到路径中
        
        // 遍历当前节点的所有邻接节点
        for (int i = h[u]; i != -1; i = nxt[i]) {
            int v = e[i]; // 获取当前邻接节点
            dfs(v, idx + 1); // 深度优先搜索
        }
        onpath[u] = 0; // DFS结束，标记该节点不在路径上
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Arrays.fill(h, -1); // 初始化邻接表头
        Arrays.fill(vis, 0); // 初始化访问标记
        Arrays.fill(onpath, 0); // 初始化路径标记
        
        n = scanner.nextInt(); // 输入边的数量
        for (int i = 0; i < n; ++i) {
            int ne = scanner.nextInt(); // 每个节点的邻接数量
            int u = scanner.nextInt(); // 输入节点编号
            vert[cntv++] = u; // 存储节点
            for (int j = 1; j < ne; ++j) {
                int v = scanner.nextInt(); // 输入目标节点编号
                add(u, v); // 添加边
            }
        }

        // 遍历所有节点进行DFS
        for (int i = 0; i < cntv; ++i) {
            dfs(vert[i], 0);
        }

        // 找到环中的最小节点以便输出
        int minu = N, idminu = -1; 
        for (int i = 0; i < nc; ++i) {
            if (cyc[i] < minu) { // 寻找最小值
                minu = cyc[i];
                idminu = i; // 记录最小值的位置
            }
        }

        // 输出环的节点，倒序打印
        for (int i = idminu, j = 0; j < nc; i = (i - 1 + nc) % nc, ++j) {
            System.out.print(cyc[i] + " "); // 输出环中的节点
        }
        System.out.println(minu); // 输出最小值作为环的结尾
    }
}

• python

MAX = 10000
n = int(input())
g = [[] for i in range(MAX)]
vis = [0] * MAX
in_stk = [0] * MAX

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(2, len(a)):
        g[a[1]].append(a[j])

stk = []
t = []
def dfs(u):
    # 这个点在本次遍历或者之前的某次遍历中被遍历过了
    if vis[u]:
        # 如果在栈中，说明本次遍历中被遍历过了
        if len(stk) > 0 and in_stk[u]:
            # 弹出元素直至弹出 u
            while len(stk) > 0 and stk[-1] != u:
                in_stk[stk[-1]] = 0
                t.append(stk[-1])
                stk.pop()
            in_stk[u] = 0
            stk.pop()
            t.append(u)
            # 找到环了，根据题意有且仅有一个环，直接退出
            return True
        else:
            return False
    vis[u] = 1
    stk.append(u)
    in_stk[u] = 1
    for v in g[u]:
        if dfs(v):
            return True
    in_stk[u] = 0
    # 这个点不在环上，需要从栈中弹出
    stk.pop()
    return False


cnt = 0
for i in range(1, MAX):
    # 依次遍历所有还未被遍历过的点
    if not vis[i]:
        if dfs(i):
            cnt += 1

if cnt > 1:
    print("oh no")

if len(t) > 0:
    # 弹出栈中的点获得的是一个倒序的环，需要反转一下
    t.reverse()
    # 题目中说了从最小的元素开始输出这个环
    minv = min(t)
    i = 0
    while i < len(t):
        if t[i] == minv:
            break
        i += 1
    ans = t[i:] + t[:i]
    ans.append(t[i])
    print(*ans)

c++

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

const int N = 100010; // 定义常量，最多支持的节点数
int n, cnt = 0, nc = 0; // n为边的数量，cnt用于边的计数，nc用于环中节点数量
int cyc[N], path[N], vis[N], onpath[N]; // cyc存储环，path存储当前路径，vis标记访问，onpath标记当前路径
int h[N], e[N << 1], nxt[N << 1]; // h为邻接表头，e为边的目标，nxt为下一条边的索引
int cntv, vert[N]; // cntv记录当前节点的数量，vert存储节点编号

// 添加边的函数
void add(int u, int v) {
    nxt[cnt] = h[u]; // 将当前边的下一条边指向当前头部
    e[cnt] = v;      // 将边的目标设置为v
    h[u] = cnt++;    // 更新头部并计数
}

// 深度优先搜索函数
void dfs(int u, int idx) {
    if (onpath[u]) { // 如果当前节点在路径上，说明找到了环
        int i = idx - 1;
        // 从路径中弹出节点，直到弹出u
        while (path[i] != u) cyc[nc++] = path[i--];
        cyc[nc++] = u; // 将u加入环中
        return;
    }
    if (vis[u]) return; // 如果已经访问过，直接返回
    vis[u] = 1; // 标记节点为已访问
    onpath[u] = 1; // 标记节点为当前路径上的节点
    path[idx] = u; // 将当前节点记录到路径中
    // 遍历当前节点的所有邻接节点
    for (int i = h[u]; ~i; i = nxt[i]) {
        int v = e[i]; // 获取当前邻接节点
        dfs(v, idx + 1); // 深度优先搜索
    }
    onpath[u] = 0; // DFS结束，标记该节点不在路径上
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); // 加速输入输出
    memset(h, -1, sizeof h); // 初始化邻接表头
    memset(vis, 0, sizeof vis); // 初始化访问标记
    memset(onpath, 0, sizeof onpath); // 初始化路径标记
    cin >> n; // 输入边的数量
    for (int i = 0; i < n; ++i) {
        int ne; // 每个节点的邻接数量
        cin >> ne; // 输入邻接数量
        int u; // 当前节点
        cin >> u; // 输入节点编号
        vert[cntv++] = u; // 存储节点
        for (int j = 1; j < ne; ++j) {
            int v; // 目标节点
            cin >> v; // 输入目标节点编号
            add(u, v); // 添加边
        }
    }

    // 遍历所有节点进行DFS
    for (int i = 0; i < cntv; ++i) {
        dfs(vert[i], 0);
    }

    // 找到环中的最小节点以便输出
    int minu = N, idminu = -1; 
    for (int i = 0; i < nc; ++i) {
        if (cyc[i] < minu) { // 寻找最小值
            minu = cyc[i];
            idminu = i; // 记录最小值的位置
        }
    }

    // 输出环的节点，倒序打印
    for (int i = idminu, j = 0; j < nc; i = (i - 1 + nc) % nc, ++j) {
        cout << cyc[i] << ' '; // 输出环中的节点
    }
    cout << minu; // 输出最小值作为环的结尾
}

javascript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    const N = 100010; // 最大节点数
    let n, cnt = 0, nc = 0; // 计数器：边数、环节点数量
    let cyc = new Array(N).fill(0), path = new Array(N).fill(0);
    let vis = new Array(N).fill(0), onpath = new Array(N).fill(0);
    let h = new Array(N).fill(-1), e = new Array(N * 2).fill(0), nxt = new Array(N * 2).fill(0);
    let cntv = 0;
    let vert = new Array(N).fill(0);

    // 添加边
    function add(u, v) {
        nxt[cnt] = h[u];
        e[cnt] = v;
        h[u] = cnt++;
    }

    // 深度优先搜索
    function dfs(u, idx) {
        if (onpath[u] === 1) { // 找到环
            let i = idx - 1;
            while (path[i] !== u) {
                cyc[nc++] = path[i--];
            }
            cyc[nc++] = u;
            return;
        }
        if (vis[u] === 1) return; // 访问过则返回
        vis[u] = 1;
        onpath[u] = 1;
        path[idx] = u;

        // 遍历邻接节点
        for (let i = h[u]; i !== -1; i = nxt[i]) {
            let v = e[i];
            dfs(v, idx + 1);
        }
        onpath[u] = 0;
    }

    // 读取输入
    n = parseInt(await readline());
    for (let i = 0; i < n; ++i) {
        let inputs = (await readline()).split(" ").map(Number);
        let ne = inputs[0], u = inputs[1];
        vert[cntv++] = u;
        for (let j = 1; j < ne; ++j) {
            let v = inputs[j + 1];
            add(u, v);
        }
    }

    // 遍历所有节点进行DFS
    for (let i = 0; i < cntv; ++i) {
        dfs(vert[i], 0);
    }

    // 找到环中的最小节点
    let minu = N, idminu = -1;
    for (let i = 0; i < nc; ++i) {
        if (cyc[i] < minu) {
            minu = cyc[i];
            idminu = i;
        }
    }

    // 逆序输出环
    let result = [];
    for (let i = idminu, j = 0; j < nc; i = (i - 1 + nc) % nc, ++j) {
        result.push(cyc[i]);
    }
    result.push(minu); // 最后再输出最小值

    console.log(result.join(" "));
    rl.close();
})();

题目描述

给定一组元素，及其依赖关系，一个元素可以依赖于多个元素(不包括自己，被依赖元素不会重复)一个元素也可被多个元素依赖。假定总是存在唯一的循环依赖，请输出该循环依赖。

输入描述

第一行一个正整数$N$，表示依赖关系的个数。

接下来每一行表示一个依赖关系，是由空格分割的多个正整数，第一个数$n$表示后面有$n$个元素，第二个数为元素编号$a$，后面多个数为$a$依赖的元素编号，任意元素$i$满足$0\lt t\lt 10000$

输出描述

一串数字，代表这个循环依赖，从最小元素编号开始，按照依赖关系依次输出，以最小元素结束。

样例

输入

3
3 1 2 5
3 2 3 4
2 3 1

输出

1 2 3 1

说明

1. 元素1依赖于2，5
2. 元素2依赖于3，4
3. 元素3依赖于1