村里有 n 户人家，编号从 1 到 n。
1 号是净水厂。
人家之间有 m 根水管，一根水管 "a b" 连接 a 号和 b 号。
水沿水管可以往任一方向流。
同样两户之间可能有多根水管，没有把一户和它自己相连的水管。
从净水厂沿水管能到达的人家都有水。
一根水管破裂时，只有这一根不能用，其余都保持原样。
对每户人家，求出有多少根水管满足：只要这一根破裂，这户就会断水。
1 号的值是 0。
一开始就没有水的人家输出 -1。
按顺序输出 1 号到 n 号的值，用空格分隔输出在一行。
7 7 1 2 2 3 3 1 3 4 4 5 4 5 5 6
0 0 0 1 1 2 -1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
只断开一条就会把图分成两部分的边叫桥（bridge）。
v 号的答案就是从净水厂到 v 的路上桥的数量——不是桥的水管断了还有别的路绕过去，而路上的桥无论走哪条路都必须经过。
一次深度优先搜索就能找出桥：记下第一次访问的次序 order[v]，以及从 v 的子树经一根非树边能回溯到的最早次序 low[v]；对子节点 w，若 low[w] > order[v]，则 v–w 是桥。
然后按访问次序（父节点总在前）用 答案[w] = 答案[父] + (是桥则 1) 填好。
每根水管轮流断开再重新搜索要 5,000 × 6,200 次，对 Python、Craykon 太慢。
陷阱一：跳过来时的那户是错的。
同样两户之间有两根水管时，一根破了另一根还能送水，所以都不是桥；但整个跳过父节点就看不到第二根水管。
例子中的 4–5 就是这样。
要传水管编号而不是户号，只跳过来时走的那一根。
陷阱二：low[w] >= order[v] 是去掉后会把图分开的点（割点）的条件。
桥要用 >——在环 1–2–3 上用 >= 会把 1–2 也误判为桥。
陷阱三：如果人家连成一条线，递归会深达 1,200 层。
Python 默认递归上限是 1,000，要用 sys.setrecursionlimit 提高；JavaScript、TypeScript、Java、C#、C、C++ 在这个深度用默认栈就够了。
Craykon 能到几千层，1,200 没问题（所以把 n 限制在 1,200）。
陷阱四：没有水的人家是 -1 而不是 0——搜索中没访问到的人家，答案保持原值不填。
语言差异：水管列表在 Python 是 [[] for _ in range(n + 1)]，Java List<List<int[]>>，C# List<(int to, int pipe)>[]，C++ std::vector<std::vector<std::pair<int, int>>>，C 用数组 head、nxt、to 串起来的邻接表（把第 i 根水管放在 2i、2i + 1 位置，水管编号就是 e / 2，不必另外记）。
Craykon 的函数可以直接读取和修改外面的变量（clock、order、low），列表最多 10,000 个元素，所以把户号减 1 从 0 号开始存（新列表(n, 0)）。
答案用 控制台.输出(answer) 写列表就会用空格连接。
import sys sys.setrecursionlimit(10000) # 집이 한 줄로 이어지면 재귀가 n단계(1,200)까지 깊어진다: 기본 한도 1,000으로는 모자란다 data = sys.stdin.read().split()n, m = int(data[0]), int(data[1])pipes = [[] for _ in range(n + 1)] # pipes[v] = (이웃, 관 번호)들for i in range(m): a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i]) pipes[a].append((b, i)) pipes[b].append((a, i)) order = [0] * (n + 1) # 깊이 우선 탐색에서 처음 들른 차례(0은 아직 안 들름)low = [0] * (n + 1) # v 아래(자식 쪽)에서 관 하나로 거슬러 닿을 수 있는 가장 이른 차례parent = [0] * (n + 1)is_bridge = [False] * (n + 1) # v와 부모를 잇는 관이 끊기면 갈라지는가visited = [] # 들른 차례대로: 부모가 늘 자식보다 앞에 있다clock = 0 def dfs(v, came_by): global clock clock += 1 order[v] = low[v] = clock visited.append(v) for w, pipe in pipes[v]: if pipe == came_by: # 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) continue if order[w] == 0: parent[w] = v dfs(w, pipe) low[v] = min(low[v], low[w]) is_bridge[w] = low[w] > order[v] # w 쪽에서 v나 그 위로 돌아올 길이 없다 else: low[v] = min(low[v], order[w]) dfs(1, -1)answer = [-1] * (n + 1)answer[1] = 0for v in visited[1:]: answer[v] = answer[parent[v]] + (1 if is_bridge[v] else 0)print(" ".join(map(str, answer[1:])))const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const pipes = Array.from({ length: n + 1 }, () => []); // pipes[v] = [이웃, 관 번호]들for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; pipes[a].push([b, i]); pipes[b].push([a, i]);} const order = new Array(n + 1).fill(0); // 깊이 우선 탐색에서 처음 들른 차례(0은 아직 안 들름)const low = new Array(n + 1).fill(0); // v 아래(자식 쪽)에서 관 하나로 거슬러 닿을 수 있는 가장 이른 차례const parent = new Array(n + 1).fill(0);const isBridge = new Array(n + 1).fill(false); // v와 부모를 잇는 관이 끊기면 갈라지는가const visited = []; // 들른 차례대로: 부모가 늘 자식보다 앞에 있다let clock = 0; function dfs(v, cameBy) { order[v] = low[v] = ++clock; visited.push(v); for (const [w, pipe] of pipes[v]) { if (pipe === cameBy) continue; // 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) if (order[w] === 0) { parent[w] = v; dfs(w, pipe); low[v] = Math.min(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } else { low[v] = Math.min(low[v], order[w]); } }} dfs(1, -1);const answer = new Array(n + 1).fill(-1);answer[1] = 0;for (const v of visited.slice(1)) answer[v] = answer[parent[v]] + (isBridge[v] ? 1 : 0);console.log(answer.slice(1).join(" "));import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;// pipes[v] = [이웃, 관 번호]들const pipes: [number, number][][] = Array.from({ length: n + 1 }, (): [number, number][] => []);for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; pipes[a].push([b, i]); pipes[b].push([a, i]);} const order: number[] = new Array<number>(n + 1).fill(0); // 깊이 우선 탐색에서 처음 들른 차례(0은 아직 안 들름)const low: number[] = new Array<number>(n + 1).fill(0); // v 아래(자식 쪽)에서 관 하나로 거슬러 닿을 수 있는 가장 이른 차례const parent: number[] = new Array<number>(n + 1).fill(0);const isBridge: boolean[] = new Array<boolean>(n + 1).fill(false); // v와 부모를 잇는 관이 끊기면 갈라지는가const visited: number[] = []; // 들른 차례대로: 부모가 늘 자식보다 앞에 있다let clock = 0; function dfs(v: number, cameBy: number): void { order[v] = low[v] = ++clock; visited.push(v); for (const [w, pipe] of pipes[v]) { if (pipe === cameBy) continue; // 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) if (order[w] === 0) { parent[w] = v; dfs(w, pipe); low[v] = Math.min(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } else { low[v] = Math.min(low[v], order[w]); } }} dfs(1, -1);const answer: number[] = new Array<number>(n + 1).fill(-1);answer[1] = 0;for (const v of visited.slice(1)) answer[v] = answer[parent[v]] + (isBridge[v] ? 1 : 0);console.log(answer.slice(1).join(" "));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.StringTokenizer; public class Main { static List<List<int[]>> pipes = new ArrayList<>(); // pipes.get(v) = {이웃, 관 번호}들 static int[] order, low, parent; // order: 처음 들른 차례(0은 아직), low: 자식 쪽에서 거슬러 닿는 가장 이른 차례 static boolean[] isBridge; // v와 부모를 잇는 관이 끊기면 갈라지는가 static int[] visited; // 들른 차례대로: 부모가 늘 자식보다 앞에 있다 static int clock = 0; static void dfs(int v, int cameBy) { order[v] = low[v] = ++clock; visited[clock - 1] = v; for (int[] p : pipes.get(v)) { int w = p[0], pipe = p[1]; if (pipe == cameBy) continue; // 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) if (order[w] == 0) { parent[w] = v; dfs(w, pipe); low[v] = Math.min(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } else { low[v] = Math.min(low[v], order[w]); } } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int v = 0; v <= n; v++) pipes.add(new ArrayList<>()); for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); pipes.get(a).add(new int[] {b, i}); pipes.get(b).add(new int[] {a, i}); } order = new int[n + 1]; low = new int[n + 1]; parent = new int[n + 1]; isBridge = new boolean[n + 1]; visited = new int[n]; dfs(1, -1); int[] answer = new int[n + 1]; Arrays.fill(answer, -1); answer[1] = 0; for (int i = 1; i < clock; i++) { int v = visited[i]; answer[v] = answer[parent[v]] + (isBridge[v] ? 1 : 0); } StringBuilder out = new StringBuilder(); for (int v = 1; v <= n; v++) { if (v > 1) out.append(' '); out.append(answer[v]); } System.out.println(out); }}using System;using System.Collections.Generic;using System.Text; class Program{ static List<(int to, int pipe)>[] pipes; // pipes[v] = (이웃, 관 번호)들 static int[] order, low, parent; // order: 처음 들른 차례(0은 아직), low: 자식 쪽에서 거슬러 닿는 가장 이른 차례 static bool[] isBridge; // v와 부모를 잇는 관이 끊기면 갈라지는가 static List<int> visited = new List<int>(); // 들른 차례대로: 부모가 늘 자식보다 앞에 있다 static int clock = 0; static void Dfs(int v, int cameBy) { order[v] = low[v] = ++clock; visited.Add(v); foreach (var (w, pipe) in pipes[v]) { if (pipe == cameBy) continue; // 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) if (order[w] == 0) { parent[w] = v; Dfs(w, pipe); low[v] = Math.Min(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } else { low[v] = Math.Min(low[v], order[w]); } } } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int m = int.Parse(first[1]); pipes = new List<(int to, int pipe)>[n + 1]; for (int v = 0; v <= n; v++) pipes[v] = new List<(int to, int pipe)>(); for (int i = 0; i < m; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(p[0]), b = int.Parse(p[1]); pipes[a].Add((b, i)); pipes[b].Add((a, i)); } order = new int[n + 1]; low = new int[n + 1]; parent = new int[n + 1]; isBridge = new bool[n + 1]; Dfs(1, -1); var answer = new int[n + 1]; Array.Fill(answer, -1); answer[1] = 0; for (int i = 1; i < visited.Count; i++) { int v = visited[i]; answer[v] = answer[parent[v]] + (isBridge[v] ? 1 : 0); } var sb = new StringBuilder(); for (int v = 1; v <= n; v++) { if (v > 1) sb.Append(' '); sb.Append(answer[v]); } Console.WriteLine(sb.ToString()); }}#include <algorithm>#include <iostream>#include <utility>#include <vector> std::vector<std::vector<std::pair<int, int>>> pipes; // pipes[v] = (이웃, 관 번호)들std::vector<int> order, low, parent; // order: 처음 들른 차례(0은 아직), low: 자식 쪽에서 거슬러 닿는 가장 이른 차례std::vector<bool> isBridge; // v와 부모를 잇는 관이 끊기면 갈라지는가std::vector<int> visited; // 들른 차례대로: 부모가 늘 자식보다 앞에 있다int clockNow = 0; void dfs(int v, int cameBy) { order[v] = low[v] = ++clockNow; visited.push_back(v); for (auto [w, pipe] : pipes[v]) { if (pipe == cameBy) continue; // 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) if (order[w] == 0) { parent[w] = v; dfs(w, pipe); low[v] = std::min(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } else { low[v] = std::min(low[v], order[w]); } }} int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; pipes.assign(n + 1, {}); for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; pipes[a].push_back({b, i}); pipes[b].push_back({a, i}); } order.assign(n + 1, 0); low.assign(n + 1, 0); parent.assign(n + 1, 0); isBridge.assign(n + 1, false); dfs(1, -1); std::vector<int> answer(n + 1, -1); answer[1] = 0; for (size_t i = 1; i < visited.size(); i++) { int v = visited[i]; answer[v] = answer[parent[v]] + (isBridge[v] ? 1 : 0); } for (int v = 1; v <= n; v++) std::cout << (v > 1 ? " " : "") << answer[v]; std::cout << '\n'; return 0;}#include <stdio.h> #define MAXN 1201#define MAXM 5000 /* 인접 목록을 배열로: 관 i는 칸 2i(a → b)와 2i+1(b → a). 칸 e의 관 번호는 e / 2 */static int head[MAXN], nxt[2 * MAXM], to[2 * MAXM];static int order[MAXN], low[MAXN], parent[MAXN]; /* order: 처음 들른 차례(0은 아직), low: 자식 쪽에서 거슬러 닿는 가장 이른 차례 */static int isBridge[MAXN]; /* v와 부모를 잇는 관이 끊기면 갈라지는가 */static int visited[MAXN]; /* 들른 차례대로: 부모가 늘 자식보다 앞에 있다 */static int answer[MAXN];static int clockNow = 0; static void dfs(int v, int cameBy) { order[v] = low[v] = ++clockNow; visited[clockNow - 1] = v; for (int e = head[v]; e != -1; e = nxt[e]) { int w = to[e]; if (e / 2 == cameBy) continue; /* 타고 온 관 하나만 건너뛴다(같은 두 집 사이의 다른 관은 거슬러 가는 길이다) */ if (order[w] == 0) { parent[w] = v; dfs(w, e / 2); if (low[w] < low[v]) low[v] = low[w]; isBridge[w] = low[w] > order[v]; /* w 쪽에서 v나 그 위로 돌아올 길이 없다 */ } else if (order[w] < low[v]) { low[v] = order[w]; } }} int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; for (int v = 1; v <= n; v++) head[v] = -1; for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); to[2 * i] = b; nxt[2 * i] = head[a]; head[a] = 2 * i; to[2 * i + 1] = a; nxt[2 * i + 1] = head[b]; head[b] = 2 * i + 1; } dfs(1, -1); for (int v = 1; v <= n; v++) answer[v] = -1; answer[1] = 0; for (int i = 1; i < clockNow; i++) { int v = visited[i]; answer[v] = answer[parent[v]] + isBridge[v]; } for (int v = 1; v <= n; v++) printf(v > 1 ? " %d" : "%d", answer[v]); putchar('\n'); return 0;}// 깊이 우선 탐색: 집 번호에서 1을 빼 0번부터 둔다(목록은 10,000칸까지)탐색(v, 타고온관){ clock += 1; order[v] = clock; low[v] = clock; visited.添加(v); 遍历 (p 在 pipes[v]) { w = p[0]; 如果 (p[1] != 타고온관) { 如果 (order[w] == 0) { parent[w] = v; 탐색(w, p[1]); low[v] = 数学.较小值(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } 否则 { low[v] = 数学.较小值(low[v], order[w]); } } }} 첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1];pipes = []; // pipes[v] = [이웃, 관 번호]들循环 (v = 0; v < n; v++){ pipes.添加([]);}循环 (i = 0; i < m; i++){ 관 = 控制台.读数字(); a = 관[0] - 1; b = 관[1] - 1; pipes[a].添加([b, i]); pipes[b].添加([a, i]);} order = 新列表(n, 0); // 처음 들른 차례(0은 아직 안 들름)low = 新列表(n, 0); // 자식 쪽에서 관 하나로 거슬러 닿을 수 있는 가장 이른 차례parent = 新列表(n, 0);isBridge = 新列表(n, 假); // v와 부모를 잇는 관이 끊기면 갈라지는가visited = []; // 들른 차례대로: 부모가 늘 자식보다 앞에 있다clock = 0; // 지금까지 들른 집의 수(함수 안에서 늘린다) 탐색(0, -1);answer = 新列表(n, -1);answer[0] = 0;循环 (i = 1; i < visited.数量; i++){ v = visited[i]; answer[v] = answer[parent[v]]; 如果 (isBridge[v]) { answer[v] += 1; }}控制台.输出(answer);