해나의 컴공생존기

1. SCC (Strongly Connected Compnent) 방향 그래프에서 임의의 두 정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 점은 같은 SCC에 속해 있다고 한다. 즉 SCC는 모든 노드가 양방향으로 Reachable한 노드의 Maximal Subset 이다. 쉽게 말하자면 x→y가 있고 y→x가 있다면 strongly conneced하다고 한다. 사이클이 이의 가장 간단한 형태이다. 여기서 Maximal 과 Maximam의 차이를 조금 짚고 넘어갈 필요가 있응 것 같다. Maximal 은 한국어로 번역하면 극대라고 할 수 있다. 그 상황에서 가장 큰 값으로 이해하자. Maximam은 전체에서 가장 큰 것을 의미한다. DFS Tree에서 여러 트리가 있을 때 하나의 트리에는 여러가..

1. Topological Sort 번역하자면 위상정렬이다. *DAG: Directed Acyclic Graph (방향성이 있고 사이클이 없는 그래프) 위상 정렬은 DAG의 노드들을 왼쪽에서 오른쪽 방향(엣지 방향이 모두 오른쪽) 으로 정렬하는 것을 의미한다. DAG에 사이클이 존재하지 않으면 알고리즘은 항상 성공한다. 사이클이 없기 위해서는 indegree=0 인 노드가 최소 하나 이상 있어야한다. 이를 귀류법으로 증명해보겠다. indgree=0인 노드가 없다고 가정해보자. indgree=0인 노드를 안만들기 위해서는 계속 들어가는 노드를 만들어야하는데, 이 과정이 무한하게 흘러간다. 무한하지 않으려면 다른노드와 연결해야하는데 이렇게 되면 사이클이 생긴다. 1.1 algorithm DAG G에서 ind..