keh0711   9달 전

처음 문제를 풀때 잡은 컨셉이 한 정점을 선택하면 이와 연결되어 같이 가야하는 정점의 수를 계산했습니다. 이렇게 문제방향을 잡으니 샘플케이스 2,3번째 케이스는 해결되지만 1번은 풀리지 않습니다.

생각해보니 버스에 탈 수 있는 자리가 넉넉할 경우, 여러 부분집합(컴포넌트)의 원소수를 조합해야 하는데...참 막막하네요

혹시나 참고가 될까하여 소스를 같이 올립니다.

koosaga   9달 전

scc로 푸는 건 쉽지 않아보입니다. 


힌트 : a가 간다 -> b도 가야한다 식의 연결관계를 그래프로 생각할 수가 있는데, 생각해보면 |V|= |E|입니다. 이러한 그래프는 특수한 모양을 가지는데, 이 모양이 도움을 줄 수 있을까요?

keh0711   9달 전

|V|= |E| 가 의미하는 바가 무엇인지, 이에 만족하는 특수한 모양의 그래프가 어떤 것인지 조금 더 자세한 설명 부탁드립니다 ^^; 

koosaga   9달 전

|V| = 정점의 개수

|E| = 간선의 개수


라는 뜻이었어요.

지금 보니 저것보다는 모든 정점의 outdegree가 1인 그래프라고 표현하는게 나은거 같긴 한데 아무튼..


https://en.wikipedia.org/wiki/Pseudoforest#Graphs_..

keh0711   9달 전

감사합니다 많은 도움이 되었습니다

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