Hoon222y

https://www.acmicpc.net/problem/4196 처음 문제를 풀때는 SCC가 뭔지도 모르고 문제를 풀었었다. 단방향인걸 모르고 양방향이라고 생각하고 Union-find했다가 광탈 해당 문제의 경우 SCC를 만들어 주고 해당 SCC로 묶은 그룹내로 들어오는 간선의 개수가 0인 경우를 세주면 되는 문제이다. 솔직히 SCC를 알았어도 삽질+못풀었을수도 있을꺼 같다. (for문에서 i대신 j 써서 진짜 개삽질 한건 ... 근데 웃긴건 앵간한 예제가 다 나왔었다 ㅋㅋ... ) 일단 문제의 경우 코사라주 알고리즘을 통해 각각 SCC를 만들어 주고 해당 정점이 어떤 SCC 그룹에 속하는지 기록해 둔다. 그 이후 모든 SCC 그룹에서 다른 그룹으로 가는 간선의 경우를 세주면 되는 문제이다. 12345..

https://www.acmicpc.net/problem/2150 SCC문제이다. SCC를 몰라서 이문제 원래는 풀생각이 없었는데 https://www.acmicpc.net/problem/4196 이 문제 단방향인줄 모르고 Union-find 쓰다가 개털려서 공부하고 풀게되었다. 문제는 그냥 SCC를 구현하는 단순한 문제라고 볼수 있다. SCC 관련 포스팅은 추후에 하도록 하겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596..