마을에 집 n채가 있고 1번부터 n번까지 번호가 붙어 있다.
1번 집은 정수장이다.
집 사이에는 수도관 m개가 있고, 수도관 하나 "a b"는 a번 집과 b번 집을 잇는다.
물은 수도관을 따라 어느 방향으로든 흐른다.
같은 두 집 사이에 수도관이 여러 개 있을 수 있고, 한 집을 자기 자신과 잇는 수도관은 없다.
정수장에서 수도관을 따라 갈 수 있는 집에는 물이 간다.
수도관 하나가 터지면 그 수도관만 못 쓰게 되고 나머지는 그대로다.
집마다, 그 수도관 하나만 터져도 그 집에 물이 끊기게 되는 수도관이 몇 개인지 구하라.
1번 집의 값은 0이다.
처음부터 물이 가지 않는 집은 -1로 출력한다.
1번부터 n번까지 집의 값을 차례로 빈칸으로 나눠 한 줄에 출력하라.
입력
첫 줄에 n과 m, 다음 m줄에 줄마다 a와 b가 빈칸으로 나뉘어 주어진다. 1 ≤ n ≤ 1,200, 0 ≤ m ≤ 5,000, 1 ≤ a, b ≤ n, a ≠ b
출력
n개의 수를 빈칸으로 나눠 한 줄에
예시 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
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
하나만 끊겨도 그래프가 둘로 갈라지는 간선을 다리(bridge)라고 해요. 집 v의 답은 정수장에서 v로 가는 길 위에 있는 다리의 수예요 — 다리가 아닌 관은 끊겨도 돌아갈 길이 있고, 길 위의 다리는 어떤 길로 가도 꼭 건너야 해요. 다리는 깊이 우선 탐색 한 번으로 찾아요: 처음 들른 차례 order[v]와, v의 자식 쪽에서 나무가 아닌 관 하나로 거슬러 닿을 수 있는 가장 이른 차례 low[v]를 적고, 자식 w에 대해 low[w] > order[v]면 v–w가 다리예요. 그다음 들른 차례대로(부모가 늘 먼저) 답[w] = 답[부모] + (다리면 1)로 채우면 돼요. 관마다 한 번씩 터뜨려 보고 다시 탐색하면 5,000 × 6,200번이라 Python·크레이콘에는 너무 느려요. 함정 하나: 타고 온 집을 건너뛰면 틀려요. 같은 두 집 사이에 관이 둘이면 하나가 터져도 다른 관으로 물이 가니 다리가 아닌데, 부모 집을 통째로 건너뛰면 두 번째 관을 못 봐요. 예시의 4–5가 그래요. 집 번호가 아니라 관 번호를 넘겨서 타고 온 관 하나만 건너뛰어요. 함정 둘: low[w] >= order[v]는 끊으면 갈라지는 집(단절점)의 조건이에요. 다리는 >예요 — 고리 1–2–3에서 >=를 쓰면 1–2도 다리라고 잘못 봐요. 함정 셋: 집이 한 줄로 이어지면 재귀가 1,200단계까지 깊어져요. Python은 기본 재귀 한도가 1,000이라 sys.setrecursionlimit으로 늘려야 하고, JavaScript·TypeScript·Java·C#·C·C++는 이 깊이면 기본 스택으로 충분해요. 크레이콘은 수천 단계까지라 1,200은 괜찮아요(그래서 n을 1,200으로 묶었어요). 함정 넷: 물이 안 가는 집은 0이 아니라 -1이에요 — 탐색에서 들르지 않은 집은 답을 채우지 않고 남겨 둬요. 언어 차이: 관 목록은 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라 따로 적을 필요가 없어요). 크레이콘은 함수가 바깥 변수(clock, order, low)를 그대로 읽고 고칠 수 있고, 목록은 10,000칸까지라 집 번호에서 1을 빼 0번부터 두어요(새목록(n, 0)). 답은 콘솔.쓰기(answer)처럼 목록을 쓰면 빈칸으로 이어져요.
Pythonmain.py · 43 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
// 깊이 우선 탐색: 집 번호에서 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);