๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon/Tree 3

[BOJ S1][C++] ๋ฐฑ์ค€ 14675๋ฒˆ: ๋‹จ์ ˆ์ ๊ณผ ๋‹จ์ ˆ์„ 

https://www.acmicpc.net/problem/14675 14675๋ฒˆ: ๋‹จ์ ˆ์ ๊ณผ ๋‹จ์ ˆ์„  ํ”„๋กœ๊ทธ๋žจ์˜ ์ž…๋ ฅ์€ ํ‘œ์ค€ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›๋Š”๋‹ค. ์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํŠธ๋ฆฌ์˜ ์ •์  ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (2 ≤ N ≤ 100,000) ํŠธ๋ฆฌ์˜ ์ •์ ์€ 1๋ฒˆ๋ถ€ํ„ฐ n๋ฒˆ๊นŒ์ง€ ์กด์žฌํ•œ๋‹ค. ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ N-1๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ„์„ ์˜ ์ • www.acmicpc.net ๋ฌธ์ œ ๊ทธ๋ž˜ํ”„ ์ด๋ก ์—์„œ ๋‹จ์ ˆ์ (cut vertex)๊ณผ ๋‹จ์ ˆ์„ (bridge)์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ ๋œ๋‹ค. ๋‹จ์ ˆ์ (cut vertex) : ํ•ด๋‹น ์ •์ ์„ ์ œ๊ฑฐํ•˜์˜€์„ ๋•Œ, ๊ทธ ์ •์ ์ด ํฌํ•จ๋œ ๊ทธ๋ž˜ํ”„๊ฐ€ 2๊ฐœ ์ด์ƒ์œผ๋กœ ๋‚˜๋‰˜๋Š” ๊ฒฝ์šฐ, ์ด ์ •์ ์„ ๋‹จ์ ˆ์ ์ด๋ผ ํ•œ๋‹ค. ๋‹จ์ ˆ์„ (bridge) : ํ•ด๋‹น ๊ฐ„์„ ์„ ์ œ๊ฑฐํ•˜์˜€์„ ๋•Œ, ๊ทธ ๊ฐ„์„ ์ด ํฌํ•จ๋œ ๊ทธ๋ž˜ํ”„๊ฐ€ 2๊ฐœ ์ด์ƒ์œผ๋กœ ๋‚˜๋‰˜๋Š” ๊ฒฝ์šฐ, ์ด ๊ฐ„์„ ์„ ๋‹จ์ ˆ์„ ์ด..

๋ฐ˜์‘ํ˜•