题目描述

给定一个网络路由图，包含$n$ 个节点（编号$1\sim n$）和$m$条无向边（编号$1\sim m$）。业务从源点$s$走到汇点$t$。 现发生$q$次故障，每次故障给出一个边编号$eid$，表示这条边失效，之后业务不能再经过它。 在每次故障发生后，需要输出“原始图中”（故障前）所有从$s$到$t$的简单路径中，有哪些路径被断开，并按以下方式编号输出：

1. 将所有$s\to t$ 的简单路径按「边编号序列」的字典序从小到大排序，依次编号为$1,2,\dots$；
2. 每次故障后，输出包含故障边的那些路径的编号（升序）。

问题本质分析

• 我们要枚举所有从$s$ 到$t$ 的简单路径，并按边编号序列的字典序排序、编号。
• 随后针对每条边$e$，需要快速知道哪些路径经过了$e$，以便在故障时输出对应的路径编号。

由于简单路径总数上限为$10^6$，我们可以：

1. DFS 枚举：从$s$开始深度优先搜索到$t$，沿途记录所经过的边编号序列。
2. 因为要按字典序枚举，需对每个节点的邻边按“边编号”升序预先排序。
3. 当 DFS 走到$t$ 时，当前的路径编号自增为$pid$，并将$pid$ 加入到该路径上每条边的关联列表 edge_paths[e] 中。
4. 最终，edge_paths[e] 即存储了所有经过边$e$的原始路径编号（自然按发现时的$pid$ 升序）。

查询时直接访问对应 edge_paths[eid]，输出其大小和内容即可。

思路步骤

1. 读入数据，构建邻接表，把边 (u,v) 同时加入 adj[u] 与 adj[v]，并记录边编号。

2. 对每个节点的邻接列表按“边编号”升序排序，确保 DFS 按字典序遍历。

3. 初始化全局变量 pid=0，一个 visited[n+1] 标记节点访问，一个 path_edges 存当前路径的边编号序列，一个 vector<int> edge_paths[m+1] 记录每条边对应的路径编号列表。

4. 从$s$开始 DFS：

   • 若到达$t$，则 pid++，并对 path_edges 中的每个边编号$e$做 edge_paths[e].push_back(pid)。
   • 否则遍历每条邻边$e$到达未访问的下一个节点，继续 DFS。

5. DFS 完毕后，针对每次故障查询，直接输出 edge_paths[eid] 的 size() 及其元素。

C++

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

int n, m, s, t;
vector<vector<pair<int,int>>> adj;      // adj[u] = list of (v, edge_id)
vector<bool> visited;                  // 访问标记
vector<int> path_edges;                // 当前 DFS 路径上的边编号
vector<vector<int>> edge_paths;        // edge_paths[e] 存经过边 e 的所有路径编号
int pid = 0;                           // 路径编号

void dfs(int u) {
    if (u == t) {
        // 到达 t，记录当前路径编号
        pid++;
        for (int e : path_edges) {
            edge_paths[e].push_back(pid);
        }
        return;
    }
    for (auto [v, eid] : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            path_edges.push_back(eid);
            dfs(v);
            path_edges.pop_back();
            visited[v] = false;
        }
    }
}

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

    cin >> n >> m >> s >> t;
    adj.assign(n+1, {});
    for (int eid = 1; eid <= m; eid++) {
        int u, v;
        cin >> u >> v;
        // 无向图
        adj[u].emplace_back(v, eid);
        adj[v].emplace_back(u, eid);
    }
    // 邻边按边编号升序，保证字典序遍历
    for (int u = 1; u <= n; u++) {
        sort(adj[u].begin(), adj[u].end(),
             [](auto &a, auto &b){ return a.second < b.second; });
    }

    visited.assign(n+1, false);
    edge_paths.assign(m+1, {});
    visited[s] = true;
    dfs(s);

    int q;
    cin >> q;
    while (q--) {
        int eid;
        cin >> eid;
        auto &vec = edge_paths[eid];
        cout << vec.size();
        for (int pid : vec) {
            cout << ' ' << pid;
        }
        cout << '\n';
    }
    return 0;
}

Python

import sys
sys.setrecursionlimit(10**7)

def main():
    input = sys.stdin.readline
    n, m, s, t = map(int, input().split())
    adj = [[] for _ in range(n+1)]     # 邻接表
    for eid in range(1, m+1):
        u, v = map(int, input().split())
        adj[u].append((v, eid))
        adj[v].append((u, eid))
    # 按边编号排序，保证字典序
    for u in range(1, n+1):
        adj[u].sort(key=lambda x: x[1])

    visited = [False] * (n+1)
    path_edges = []                     # 当前路径上的边
    edge_paths = [[] for _ in range(m+1)]
    pid = 0

    def dfs(u):
        nonlocal pid
        if u == t:
            pid += 1
            for e in path_edges:
                edge_paths[e].append(pid)
            return
        for v, eid in adj[u]:
            if not visited[v]:
                visited[v] = True
                path_edges.append(eid)
                dfs(v)
                path_edges.pop()
                visited[v] = False

    visited[s] = True
    dfs(s)

    q = int(input())
    for _ in range(q):
        eid = int(input())
        vec = edge_paths[eid]
        # 输出断开路径数及其编号
        print(len(vec), *vec)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n, m, s, t;
    static List<int[]>[] adj;           // adj[u]: list of {v, eid}
    static boolean[] visited;
    static List<Integer> pathEdges = new ArrayList<>();
    static List<List<Integer>> edgePaths;
    static int pid = 0;

    static void dfs(int u) {
        if (u == t) {
            pid++;
            for (int e : pathEdges) {
                edgePaths.get(e).add(pid);
            }
            return;
        }
        for (int[] ve : adj[u]) {
            int v = ve[0], eid = ve[1];
            if (!visited[v]) {
                visited[v] = true;
                pathEdges.add(eid);
                dfs(v);
                pathEdges.remove(pathEdges.size() - 1);
                visited[v] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        adj = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int eid = 1; eid <= m; eid++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj[u].add(new int[]{v, eid});
            adj[v].add(new int[]{u, eid});
        }
        // 按边编号排序
        for (int i = 1; i <= n; i++) {
            adj[i].sort(Comparator.comparingInt(a -> a[1]));
        }

        visited = new boolean[n+1];
        edgePaths = new ArrayList<>();
        for (int i = 0; i <= m; i++) edgePaths.add(new ArrayList<>());

        visited[s] = true;
        dfs(s);

        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int eid = Integer.parseInt(br.readLine());
            List<Integer> vec = edgePaths.get(eid);
            sb.append(vec.size());
            for (int id : vec) {
                sb.append(' ').append(id);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

题目内容

网络路由图由 $n$ 个点(编号从 $1$ 开始依次递增)和 $m$ 条边(编号从 $1$ 开始依次递增)构成，业务的流量由 $s$ 点走到 $t$ 点。

现在网络发生了 $q$ 次故障，每次故障给出一个整数 $i$ ，表示第 $i$ 条边发生了故障，业务将不能再经过这条边。

每次故障发生后，输出 $s$ 到 $t$ 的哪些简单路径被断开了。

$s$ 到 $t$ 的简单路径是一条点和边都不重复出现的路径。

$s$ 到 $t$ 的简单路径由一个边序列 $eid1,eid2,...,eidk$ 构成，$eid$ 代表 $edgeld$

为避免输出量过大，我们将原始图中的路径(故障发生前)按照边序列的字典序从小到大排序，依次编号为 $1,2,3,...$

每次故障发生后，只需要输出这些边的编号即可(从小到大排序)

在比较数组的字典序时，遵循以下规则：

1.从第一个元素开始，逐个比较数组对应位置的元素。

2.如果某个位置的元素不相同，较小的元素所在的数组排在前面。

3.如果所有比较位置的元素都相同，则较短的数组排在前面。

例如，给定两个数组 $[1,2,3]$ 和 $[1,2,4]$ ，由于在第三个位置上 $3< 4$ ，因此 $[1,2,3]$ 在字典序中排在 $[1,2,4]$ 之前。

如果比较 $[1,2]$ 和 $[1,2,0]$ ，由于前两个位置的元素相同，而第一个数组较短，因此 $[1,2]$ 在字典序中排在 $[1,2,0]$ 之前。

输入描述

第一行给出 $4$ 个整数 $n,m,s,t(2<=n<=500,1<=m<=1000,1<=s,t<=n,s<=t)$

第 $2$ 到 $m+1$ 行每行两个整数 $u,v$ 表示点 $u$ 和点 $v$ 之间有一条无向边,边按输入顺序编号为 $1,2,...,m$

第 $m+2$ 行给出一个整数 $q(1<=q<=m)$ 表示故障的发生次数

接下来 $q$ 行每行一个整数 $eid(edgeld)$ 表示编号为 $eld(1<=eld<=m)$ 的边发生了故障，保证所有的 $eld$ 互不相同

输入保证 $s$ 到 $t$ 的简单路径不超过 $1000000$ 条,保证以 $s$ 为起点不经过点 $t$ 的简单路径不超过 $10000000$ 条

输出描述

输出 $q$ 行，每行依次对应该次故障的答案

每行首先输出一个整数 $x$ 表示本次故障共有 $x$ 条路径被断开，接下来 $x$ 整数为这些被断开的路径的编号(升序输出)，单空格间隔

样例1

输入

2 2 1 2
1 2
1 2
2
2
1

输出

1 2
1 1

说明

样例2

输入

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

输出

0
2 2 3
1 1

说明

如图：

从 $1$ 到 $2$ 一共有 $3$ 条简单路径：$1->2，1->3->2，1->3->4->2$

$3$ 条路径的边序列分别为：$1$, $2$ $3$, $2$ $4$ $5$

因此按照字典序依次编号为：$1,2,3$

当断掉第 $6$ 条边 $(1->5)$，没有路径被断开

断掉第 $2$ 条边，路径 $2$ 和 $3$ 被断开

断掉第 $1$ 条边，路径 $1$ 被断开