강한 연결 요소(SCC)

그래프에셔 u->v와 v->u 경로(간선아님)가 모두 있으면 같은 SCC에 속한다고 한다.

dfs하면서 stack을 이용해서 분리해 낸다. 선형시간 O(n)

 

필요한 것:

 int id = 0, dfsn[MAX]={0};  //방문하는 정점마다 고유번호를 저장하기 위함. dfsn은 visit의 역할도 수행한다.

 bool finished[MAX] = {false}; //scc추출이 완료된 정점인지 

 vector<int> adj[MAX]

 stack<int> s

 선택1) vector<vector<int>> SCC;

 선택2) int SN=0, sn[MAX]; //해당 정점이 포함된 scc번호를 저장함

 

int id, dfsn[MAX];
bool finished[MAX];
vector<int> adj[MAX];
vector<vector<int>> SCC;
stack<int> s;

int makeSCC(int curr) {
	dfsn[curr] = ++id;
	s.push(curr);

    //curr 정점의 부모정점(dfs트리상)중 가장 작은 번호. 초기값:자기자신
	int parent = dfsn[curr];
	for (auto next : adj[curr]) {
        //다음 방문할 정점이 아직 방문되지 않은 경우
		if (dfsn[next] == 0) parent = min(parent, makeSCC(next));
        //다음 방문할 정점이 방문됐으나 scc추출이 끝나지 않은 경우
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}
	if (parent == dfsn[curr]) {
		vector<int> scc;
		while (1) {
			int t = s.top();
			s.pop();
			finished[t] = true;
			scc.push_back(t);
			if (t == curr) break;
		}
		sort(scc.begin(), scc.end());
		SCC.push_back(scc);
	}

	return parent;
}

 

두번째 버전.

if(parent == dfsn[curr]){
	while(1){
    	int t = s.top();
        s.pop();
        finished[t] = true;
        sn[t] = SN;  //scc번호 부여
        if(t==curr) break;
    }
    SN++;
}    
        

 

 

기본문제:

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

2150번: Strongly Connected Component