村に家が 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
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);