sgc109   3달 전

SCC에 대해 공부를 하고 예제를 하나씩 풀어보는 중에 이 문제를 접하게됐습니다.

문제를 읽어보니 주어진 방향그래프내에 있는 SCC들을 하나의 SCC로 묶기위해 필요한 방향간선의 최소 개수를 출력하라는 것으로 이해했습니다.

그래프 압축을 통해 새롭게 생성된 DAG에서 모든 정점들을 하나의 SCC로 묶어야할것같은데 풀이방법이 명확하게 잘 떠오르지 않네요.. 힌트좀부탁드립니다.

그리고 제가 나름 소스를 짜서 테스트 케이스를 여러가지 만들어서 넣어봐도 맞게 나오는것같은데 틀린입력 하나만 가르쳐주시면 감사드리겠습니다.

pinch3773   3달 전

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


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

pinch3773   3달 전

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

pinch3773   3달 전

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

sgc109   3달 전

저도 그런식으로 했습니다. 문제는 주어진그래프를 압축시킨 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을뺌) 제가 태스트해본 입력값들에대해선 올바른답을내는데 틀렸습니다가 뜹니다ㅠㅠ 좀 말이 많이 복잡한가요..?

sgc109   3달 전

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

pinch3773   3달 전

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

pinch3773   3달 전

위에 말씀은 우선 

(1)

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

(2)

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


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

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

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

pinch3773   3달 전

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

sgc109   3달 전

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

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

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

sgc109   3달 전

아 반례 찾았네요

1

6 4

1 2

1 3

4 6

5 6


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

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