강한 연결 요소 (Strongly Connected Component)

강한 연결 요소 (Strongly Connected Component)는 SCC라고 불리는 알고리즘 입니다.

유향 그래프에서 특정 노드에서 다른 노드들을 걸쳐 다시 특정노드로 돌아올 수 있으면, 노드들이 강하게 연결되어 있다 라고 합니다.

DFS를 배우셨다면, 조금 쉽게 이해하실 수 있을거 같습니다.

 

ex)

https://www.acmicpc.net/problem/26146

26146번: 즉흥 여행 (Easy)

1에서 2를 걸쳐 3으로 갔다가 다시 1로 돌아올 수 있음, 1에서 4로 갔다가 다시 돌아올 수 있음

그러므로 모든 노드는 연결되어 있다고 볼 수 있습니다.

 

<자바>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static boolean[] visited;
	static Stack<Integer> stack = new Stack<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int v = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken());
		
		visited = new boolean[v + 1];
		ArrayList<Integer>[] graph = new ArrayList[v + 1], reversegraph = new ArrayList[v + 1];
		
		for(int i = 1; i <= v; i++) {
			graph[i] = new ArrayList<>();
			reversegraph[i] = new ArrayList<>();
		}
		
		while(e --> 0) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken()), to = Integer.parseInt(st.nextToken());
			
			graph[from].add(to);	//가는 방향대로 저장
			reversegraph[to].add(from);	//가는 방향의 반대로 저장
		}
		
		for(int i = 1; i <= v; i++) {
			if(!visited[i]) {
				dfs(i, graph, true);
			}	//방문 하지 않았다면 dfs로 방문
		}
		
		Arrays.fill(visited, false);	//역으로 재방문 할것이므로, 모든 visited는 false로 처리
		
		dfs(stack.pop(), reversegraph, false);	//스택에 저장된 첫 노드를 꺼내 역으로 재방문
		//해당 문제는 모두 연결되어 있는지 확인하는 것이므로 1번만 꺼내지만, 다른 문제들은 다를 수 있음
		
		String answer = "Yes";
		while(!stack.isEmpty()) {
			if(!visited[stack.pop()]) {
				answer = "No";
				break;
			}
		}// 스택이 비어있을때까지 꺼내는데, 방문하지 않았다면 모두 연결되어 있지 않으므로 No
		
		System.out.print(answer);
	}
	
	public static void dfs(int depth, ArrayList<Integer>[] graph, boolean check) {
		visited[depth] = true;
		
		for(int a : graph[depth]) {
			if(!visited[a]) {
				dfs(a, graph, check);
			}
		}// 기본 dfs
		
		if(check) {
			stack.add(depth);
		}// 정방향 그래프일 경우에만 stack에 저장
	}
}

 

SCC에 대한 자세한 사항은 해당 블로그를 확인해주세요.

https://yjg-lab.tistory.com/188

[알고리즘] 강한 연결 요소 추출 알고리즘 (Strongly Connected Component)