[๋ฐฑ์ค€] 2252 : ์ค„ ์„ธ์šฐ๊ธฐ - java [์ž๋ฐ”]

https://www.acmicpc.net/problem/2252 2252๋ฒˆ: ์ค„ ์„ธ์šฐ๊ธฐ ์ฒซ์งธ ์ค„์— N(1 โ‰ค N โ‰ค 32,000), M(1 โ‰ค M โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. M์€ ํ‚ค๋ฅผ ๋น„๊ตํ•œ ํšŒ์ˆ˜์ด๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ํ‚ค๋ฅผ ๋น„๊ตํ•œ ๋‘ ํ•™์ƒ์˜ ๋ฒˆํ˜ธ A, B๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋Š” ํ•™์ƒ A๊ฐ€ ํ•™์ƒ B์˜ ์•ž์— ์„œ์•ผ ํ•œ๋‹ค๋Š” ์˜ www.acmicpc.net ํ’€์ด "์—ฐ๊ฒฐ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„ N๋ช…์˜ ํ•™์ƒ ์ค„ ์„ธ์šฐ๊ธฐ"๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ•ด์„ํ•  ์ˆ˜ ์žˆ๋‹ค. => ์—ฐ๊ฒฐ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„ ์ˆœํ™˜ํ•˜์ง€ ์•Š๋Š” ๋ฐฉํ–ฅ์„ฑ ๊ทธ๋ž˜ํ”„(DAG=๋ฐฉํ–ฅ์„ฑ ๋น„์ˆœํ™˜ ๊ทธ๋ž˜ํ”„)์—์„œ ๊ฐ ๋…ธ๋“œ๋ฅผ ์ค„ ์„ธ์šฐ์‹œ์˜ค. ์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์œ„์ƒ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ผ์น˜ํ•˜๋ฏ€๋กœ ์œ„์ƒ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด ํ’€์ดํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ๋Š” ๊ฐ ๋…ธ๋“œ์˜ ์—ฐ๊ฒฐ ๋‹นํ•œ ์ •๋ณด๋ฅผ linked ๋ฐฐ์—ด์— ๋ฏธ๋ฆฌ ์ž…๋ ฅ ํ›„ ..
PS/๋ฐฑ์ค€ 2022. 2. 27. 12:06
1