그냥 드는 생각인데(아직 풀지는 않았지만) DAG를 scc로 묶어서 만든 다음, 이 DAG를 위상 정렬 한다음에 ,맨 끝 점에서 indegree가 0인 맨 처음 점으로 간선 하나만 추가하면 되지 않을까요?

저도 풀어보고 말씀드릴께요 과제만 다하고요 ;;

아 아니네요 상황에 따라서 더 추가해야 할 경우도 있겠네요 ;;

DAG에서 out degree가 0인 component 들을 모두 각각 in degree가 0인 component에 연결 하면 되려나요...?

저도 그런식으로 했습니다. 문제는 주어진그래프를 압축시킨 DAG들의 모든 정점들이 하나의 덩어리로 되어있지않을수도있어서.. 서로다른 덩어리(DAG)G1,G2를 연결할때 G1에서 out degree 가 0인 점중 하나와 G2에서 in degree 가 0인 점 하나를 잇고  G1에서 out degree 가 0인 나머지 점들은 방금 이은 점으로 간선을 추가하는 식으로한뒤 모든 덩어리를 다 연결한뒤 마지막으로 또 out degree 가 0인 점들중 하나로 다 간선을긋고 그 하나에서 in degree 가 0인 모든점들로 간선을 그을때  지금까지 간선을 그은 총 횟수를 출력하게했는데(단처음에 scc의 개수가 1개일땐 마지막에1을뺌) 제가 태스트해본 입력값들에대해선 올바른답을내는데 틀렸습니다가 뜹니다ㅠㅠ 좀 말이 많이 복잡한가요..?

@pinch3773

음.. 쉽게말해서 주어진 그래프를 SCC단위로 DAG 로 압축시켰을때 여러개의 연결되지않은 그래프들이 나오잖아요? 그 그래프들을 in degree0인 정점과 out degree0인 정점을이음으로서 하나로 다연결한뒤 한덩어리가되면 거기서 또 out 0 인 점 에서 in 0 인점들로 다 잇는식으로했습니다(물론 각각의 덩어리에서 out0인 점이 여러개일경우 잇는데 사용되지않은 점들은 잇는데 사용된 점으로 모두간선을 이엇고 in0인 점이여러개면 다 모아둿다가 마지막에 한덩이가되엇을때 out이0인점즁하나에서 한꺼번에 간선을이엇습니다..) 이거 틀린방법일까요..?

아 그렇군요 DAG가 꼭 weakly connected 라는 보장이 없군요 음.... 더 생각해 봐야겠네요.

위에 말씀은 우선 

(1)

DAG 의 형태를 띄고 있는 weakly connected component(이하 wcc) 각각의 indegree가 0인 점과  outdegree가 0인 점을 모두 이은 다음,

(2)

또 다시 각각의 덩어리 component들의 out 0인 점들과 in 0인 점을 서로 잇는다는 말씀이시죠?

그런데 2번 과정에서 반드시 다 이을 필요가 있을 까요 ? (1)번 과정을 수행한 다음은, 

각각의 wcc들은 (1)번 과정에서 하나의 scc로 다시 만들어 졌고, 그 다음은 각각의 scc를 

사이클의 형태로 scc의 개수의 간선만을 연결해주면 더 적은 간선으로 전체 scc를 만들 수 있지 않을까요?

음 그런데 제가 이해 한게 맞다면 ... (1)번 과정에서 이미 in이 0인 점과 out이 0인 점은 이미 다 없어지는 것 아닌가요? (2)번 과정은 어떻게 수행되는 것이죠?

@pinch3773 아 1번과정이 모든 점들을 다잇는게아니고

음 만약 DAG로 만든뒤라고해도

애초에 간선으로 연결이 되지않은 그래프들이 여러개가 나올수가있으니 그래프가 1개이상 나오잖아요? 그럼 하나씩(덧셈에서 누적시키는느낌으로) 붙여나가는데 각각 붙일때마다 한덩이에선 in0인 점하나 그리고 한덩이에선 out0인 점하나만 간선하나를추가해서 잇는다는말을한거엿어요! 혹시 제가짠 소스에서 잘못된출력이나오는 입력케이스가 아시나요?ㅠ

아 반례 찾았네요

1

6 4

1 2

1 3

4 6

5 6

일때 3이 나와야할텐데 4가나올것같네요..

매우 오래된 질문에 의문점을 남겨서 죄송합니다만 이 문제에 대해 질문이 이것밖에없는지라 질문올려봅니다.

이문제가 왜 scc 를 이용해야하는것인지 그리고 단순히 scc를 구하는것이 아닌 뒤에 추가적인 작업을 하는데 이작업의 의미는 무엇인지 알 수 있을까요??

단순히 scc가 어떤것이다만 배웟지 어디에 사용하는지를 잘 모르겟습니다.