3 solutions

  • 0
    @ 6 months ago 
    from collections import defaultdict

def find_cycle(dependencies):
    graph = defaultdict(list)  # 用邻接表表示图
    for dep in dependencies:
        a = dep[1]  # 元素a
        for i in range(2, len(dep)):  # a依赖的元素们
            graph[a].append(dep[i])
    
    visited = [0] * 10000  # 假定元素编号不超过10000
    path = []
    cycle_path = []
    
    # 寻找环的DFS函数
    def dfs(node, trace):
        nonlocal cycle_path
        visited[node] = 1  # 标记为正在访问
        trace.append(node)  # 将当前节点加入路径
        
        for neighbor in graph[node]:
            if visited[neighbor] == 0:  # 如果邻居节点未访问过，递归访问
                if dfs(neighbor, trace):
                    return True
            elif visited[neighbor] == 1:  # 如果邻居节点正在访问中，说明存在环
                cycle_start_idx = trace.index(neighbor)  # 找到环的起点
                cycle_path = trace[cycle_start_idx:]  # 获取环的路径
                return True
        
        visited[node] = 2  # 标记为已访问
        trace.pop()  # 回溯
        return False
    
    # 遍历所有节点，寻找环
    for dep in dependencies:
        a = dep[1]
        if visited[a] == 0:  # 如果该元素未被访问过
            if dfs(a, path):
                break
    
    # 输出环，确保从最小编号元素开始
    if cycle_path:
        cycle_start = min(cycle_path)  # 找到环中最小的元素
        start_idx = cycle_path.index(cycle_start)
        cycle_path = cycle_path[start_idx:] + cycle_path[:start_idx]  # 重新排列环
        cycle_path.append(cycle_start)  # 确保以最小编号元素结束
        print(" ".join(map(str, cycle_path)))

# 输入
n = int(input())  # 依赖关系的个数
dependencies = [list(map(int, input().split())) for _ in range(n)]

# 寻找并输出环
find_cycle(dependencies)
    Copy
    • 0
      @ 8 months ago

      DFS拓扑循环 参考hot100题库中 循环数组 + 课程表II相关的组合题 需要注意的是 构建图的时候 数字元素是 < 10000

      #include<bits/stdc++.h>

using namespace std;
vector<vector<int>> graph;
vector<bool> onPath;
vector<bool> visited;
vector<int> headNode;
bool hasCycle = false;
vector<int> postOrder;

void rotate(vector<int>& nums, int k) {
    // 法1
    // k %= nums.size();
    // reverse(nums, 0, nums.size() - 1);
    // reverse(nums, 0, k - 1);
    // reverse(nums, k, nums.size() - 1);

    // method 2
    int n = nums.size();
    k = k % n;
    vector<int> cp(n , 0);
    for (int i = 0; i < n; i++) {
        cp[(i + k) % n] = nums[i];
    }
    nums.assign(cp.begin(), cp.end());
}

void traverse(vector<vector<int>>& graph, int s) {
    if (onPath[s]) hasCycle = true;
    if (visited[s] || hasCycle) return;
    visited[s] = true;
    onPath[s] = true;
    for (int t: graph[s]) {
        traverse(graph, t);
    }
    postOrder.push_back(s);
    onPath[s] = false;
}

int main() {
    int N; cin >> N;
    graph = vector<vector<int>>(10005);
    headNode.resize(N);
    for (int i = 0; i < N; i++) {
        int n; cin >> n;
        vector<int> nums(n);
        int from = -1;
        for (int j = 0; j < n; j++) {
            cin >> nums[j];
            if (j == 0) {
                from = nums[j];
                headNode[i] = nums[j];
            }
            else if (j > 0){
                graph[from].push_back(nums[j]);
            }
        }
    } // build graph
    onPath.resize(10005, false);
    visited.resize(10005, false);
    // 3296 8872 8024 6761 9263 9433 
    for (int i = 0; i < N; i++) {
        int from = headNode[i];
        traverse(graph, from);
    }
    reverse(postOrder.begin(), postOrder.end()); // 初始顺序 
    // 需要找到最小值
    int min_val = 10005, pos = 0;
    for (int i = 0; i < postOrder.size(); i++) {
        if (min_val > postOrder[i]) {
            pos = i;
            min_val = postOrder[i];
        }
    }
    int nums = postOrder.size();
    rotate(postOrder, nums - pos);
    for (int v: postOrder) {
        cout << v << " ";
    }
    cout << postOrder[0] << endl;
    return 0;
}
      Copy
      • 0
        @ 8 months ago

        题面描述:

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

        思路

        简化题意：给出若干条边组成的有向图，找出其中唯一的环，保证环一定存在。 直接 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); // 输出最小值作为环的结尾
    }
}
        Copy
        • 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)
        Copy

        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; // 输出最小值作为环的结尾
}
        Copy
        • 1

        2024.03.20-暑期实习-第三题-循环依赖

        Information

        ID
        81
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        7
        Tags
        # Submissions
        183
        Accepted
        42
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 京ICP备2025123107号-1
        3. Worker 0, 83ms
        4. Powered by Hydro v4.18.0 Community