A village has n houses numbered 1 to n.
House 1 is the water plant.
There are m water pipes between houses, and a pipe "a b" connects house a and house b.
Water flows along a pipe in either direction.
There may be several pipes between the same two houses, and no pipe connects a house to itself.
A house gets water if it can be reached from the water plant along pipes.
When one pipe bursts, only that pipe becomes unusable and all the others stay as they are.
For each house, find how many pipes have the property that the burst of that one pipe alone would cut off the water to that house.
The value for house 1 is 0.
Print -1 for a house that gets no water to begin with.
Print the values for houses 1 to n in order, on one line separated by spaces.
Input
The first line has n and m, and each of the next m lines has a and b, separated by a space. 1 ≤ n ≤ 1,200, 0 ≤ m ≤ 5,000, 1 ≤ a, b ≤ n, a ≠ b
Output
n numbers on one line, separated by spaces
Example 1 · stdin
7 7
1 2
2 3
3 1
3 4
4 5
4 5
5 6
stdout
0 0 0 1 1 2 -1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
An edge whose removal alone splits the graph is a bridge. The answer for house v is the number of bridges on the way from the plant to v — a pipe that is not a bridge has a way around it, and every bridge on the way must be crossed whichever way you go. One depth-first search finds the bridges: record the visit order order[v] and low[v], the earliest order reachable from v's subtree by one non-tree pipe; for a child w, v–w is a bridge when low[w] > order[v]. Then, in visit order (a parent always comes first), fill answer[w] = answer[parent] + (1 if bridge). Bursting each pipe in turn and searching again is 5,000 × 6,200 steps, too slow for Python and Craykon. Trap one: skipping the house you came from is wrong. With two pipes between the same two houses, one can burst and water still flows through the other, so neither is a bridge, but skipping the parent house altogether never sees the second pipe. Pipes 4–5 in the example are like this. Pass the pipe number, not the house number, and skip only the one pipe you came by. Trap two: low[w] >= order[v] is the condition for a house whose removal splits the graph (an articulation point). Bridges use > — on the loop 1–2–3, >= wrongly calls 1–2 a bridge. Trap three: if the houses form one line, recursion goes 1,200 levels deep. Python's default recursion limit is 1,000, so raise it with sys.setrecursionlimit; JavaScript, TypeScript, Java, C#, C and C++ manage this depth with their default stacks. Craykon handles a few thousand levels, so 1,200 is fine (that is why n is capped at 1,200). Trap four: a house with no water is -1, not 0 — leave the answer of houses the search never visits as it was. Language differences: the pipe lists are 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>>>, and in C an adjacency list linked through the arrays head, nxt and to (putting pipe i in slots 2i and 2i + 1 makes the pipe number e / 2, so it need not be stored). In Craykon a function can read and change outer variables (clock, order, low) directly, and lists hold up to 10,000 items, so it subtracts 1 from each house number to start at 0 (NewList(n, 0)). Writing the list as Console.WriteLine(answer) joins it with spaces.
Pythonmain.py · 43 lines
import syssys.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 = 0def 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:])))
JavaScriptmain.js · 37 lines
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(" "));
TypeScriptmain.ts · 40 lines
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(" "));
JavaMain.java · 68 lines
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); }}
C#Main.cs · 71 lines
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()); }}
C++main.cpp · 55 lines
#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;}
Cmain.c · 56 lines
#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;}
Craykonmain.cray · 64 lines
// 깊이 우선 탐색: 집 번호에서 1을 빼 0번부터 둔다(목록은 10,000칸까지)탐색(v, 타고온관){ clock += 1; order[v] = clock; low[v] = clock; visited.Add(v); foreach (p in pipes[v]) { w = p[0]; if (p[1] != 타고온관) { if (order[w] == 0) { parent[w] = v; 탐색(w, p[1]); low[v] = Mathf.Min(low[v], low[w]); isBridge[w] = low[w] > order[v]; // w 쪽에서 v나 그 위로 돌아올 길이 없다 } else { low[v] = Mathf.Min(low[v], order[w]); } } }}첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];pipes = []; // pipes[v] = [이웃, 관 번호]들for (v = 0; v < n; v++){ pipes.Add([]);}for (i = 0; i < m; i++){ 관 = Console.ReadNumbers(); a = 관[0] - 1; b = 관[1] - 1; pipes[a].Add([b, i]); pipes[b].Add([a, i]);}order = NewList(n, 0); // 처음 들른 차례(0은 아직 안 들름)low = NewList(n, 0); // 자식 쪽에서 관 하나로 거슬러 닿을 수 있는 가장 이른 차례parent = NewList(n, 0);isBridge = NewList(n, false); // v와 부모를 잇는 관이 끊기면 갈라지는가visited = []; // 들른 차례대로: 부모가 늘 자식보다 앞에 있다clock = 0; // 지금까지 들른 집의 수(함수 안에서 늘린다)탐색(0, -1);answer = NewList(n, -1);answer[0] = 0;for (i = 1; i < visited.Count; i++){ v = visited[i]; answer[v] = answer[parent[v]]; if (isBridge[v]) { answer[v] += 1; }}Console.WriteLine(answer);