재원블로그 재원블로그

이 문제는 유향 그래프의 강한 연결 요소들을 찾는 기본 문제이다. 딱히 주의할 점은 없지만 하나 있다면 출력에서 각 강한 연결 요소들 안에서의 정렬도 해야하지만 강한 연결 요소들간의 정렬도 필요하다는 것이다. 강한 연결 요소를 찾는 알고리즘은 O(V + E)인데, 이 문제의 입력은 V 가 최대 10000, E가 최대 100000이므로 2초의 시간이면 충분하다. #include #include #include #include using namespace std; int v, e; vector edges[10001]; vector transpose[10001]; vector visited; stack st; vector tempNodes; vector answer; void dfs(int start) { v..

유향 그래프에서 모든 정점이 도달 가능하면 강하게 연결되었다고 한다. 여기서 강한 연결 요소는 부분 그래프의 모든 정점이 강하게 연결된 것이다. 강한 연결 요소를 찾는 것은 O(V + E) 시간에 가능하다. Transpose graph가 이를 찾는 알고리즘에서 사용되는데, 이는 원래 그래프의 모든 간선의 방향이 반대인 그래프이다. 강한 연결 요소를 찾는 알고리즘은 다음과 같다. 1. DFS를 수행한다. 2. DFS를 수행하고 각각이 끝날 때마다 스택에 집어넣는다. 3. Transpose graph에 대해서 DFS를 수행한다. 이 때 시작점은 스택에서 pop하는 순서대로이다. 4. DFS가 끝날 때마다 저장한다. 이를 C++로 구현하면 다음과 같다. int v, e; vector edges[10001]; ..