plzrun   7년 전

주석에 이쁘게 어떻게 코딩했는지 썼으나,

짧게 코멘트를 더해보자면, :)


위상정렬로 풀었습니다.


처음에 인접리스트로 그래프를 받고나서 (v라는 변수에 받아요)

start부터 dfs돌면서 다시 g라는 변수에 그래프를 그려줍니다. 이때 해당 정점의 in-degree를 셌어요.


그 다음 위상정렬 방식처럼 인디그리가 0이되면 큐에 넣고.. 뭐 이런방식을 계속 씁니다.

(싸이클이 없고 일방통행이니까 그래프는 DAG라는 것이고,

그래프에서 start를 거치지 않고 end로 향하는 길이 있을 수 있기 때문에

초기에 dfs를 돌려서 그래프를 다시 생성했거든요.)


ㅠㅠ 고통받는 저를 구원해주세요 ㅠㅠ

어쩜 하나도 그냥 풀리는 게 없을까요 ㅠ?

plzrun   7년 전

네.. doju님 덕에 또 해결 ㅋㅋ


1->2->3->5

2->4->5

이런식으로 모든 가중치가 1일때

도로의 개수가 5가 나와야 하는데 6이나오게 짰더라구요.


그래서 맥스구할때 parent저장하고

그 parent따라서 dfs돌리면서 도로 개수 세줬습니다.


도주님 감사. :D

댓글을 작성하려면 로그인해야 합니다.