백준 2150 (Strongly Connected Component) c++

문제

2150번: Strongly Connected Component

SCC알고리즘를 사용하여 주어진 방향 그래프에서 SCC의 갯수와 각각의 SCC 구성 노드를 차례대로 출력하는

문제 입니다.

 

 SCC를 추출해주는 알고리즘은 타잔 알고리즘을 사용 하였습니다.

 

vector<ll>v[10001]; //주어진 그래프 정보 저장
ll dfsn[10001];//방문 순서를 저장할 배열
ll scc_count; //scc의 갯수를 세는 변수
ll sn[10001]; //x번 정점이 몇번째 scc에 포함되어 있는지 알려주는 배열
vector<vector<ll>>SCC; //SCC를 벡터로 저장한 벡터의 벡터
stack<ll>st;
bool fin[10001];//x번쨰 정점이 scc추출이 끝났는지 확인

먼저 사용되는 배열과 변수를 보겠습니다.

1) 벡터 v는 주어진 방향 그래프를 저장하는 용도입니다. 예를 들어 v[a] = b : a번 노드에서 b번 노드로 향하는 간선이

존재 한다는 의미 입니다.

2) dfsn 배열은 각 노드 마다 방문 순서를 저장하는 배열 입니다. 예를 들어 dfsn[1] = 1 : 1번 노드를 첫번째로 방문

한다는 의미 입니다.

3) scc_count는 scc의 갯수를 세는 변수 입니다. 

4) sn배열은 임의의 정점이 몇번째 scc에 포함되어 있는지 저장하는 배열입니다. 

예를 들어 4번째 scc가 {1, 2, 5}번 노드로 구성되어 있다면 sn[1] = sn[2] = sn[5] = 4 입니다.

5) SCC벡터는 각각의 scc를 저장하는 벡터의 벡터입니다. 

예를들어 scc가 {1, 2, 5}, {7, 8, 9} 총 2개 가 있다면 SCC[0] = {1, 2, 5}, SCC[1] = {7, 8, 9}가 됩니다.

6) st 스텍은 탐색하는 노드들을 넣어주고 scc가 완성되면 scc의 구성된 노드들을 st에서 삭제할 것입니다.

7) fin 배열은 scc추출이 끝났는지 검사하는 배열입니다. 

예를들어 scc가 {1, 2, 5}면 fin[1] = fin[2] = fin[5] =true가 됩니다. 나중에 cross edge 또는 forward edge를 무시하기

위함 입니다.

for (int i = 1; i <= V; i++)
	if (!dfsn[i])dfs(i); //방문하지 않은 정점들을 방문

main 함수에서 모든 정점과 간선의 정보를 입력받으면 위의 for문을 실행해 줍니다.

모든 정점을 방문하기 위함으로 dfsn[i]가 아무정보도 없으면 dfs를 실행해줍니다.

만약 1번 정점으로 부터 모든 정점들이 연결되어있다면 dfs(1) 한번만 실행하면 상관없습니다.

하지만 모든 그래프가 연결되어있다는 보장이 없기 때문에 다음과 같은 for문을 실행하면서 

모든 정점을 검사하는 것입니다.

ll dfs(ll x) { //x와 x의 자손들 중 올라갈 수 있는 최소의 dfsn값을 return(제일 위로 어디까지 갈 수 있는지)
    dfsn[x] = ++cnt; //방문순서를 계속해서 저장
    st.push(x);
    ll ret = dfsn[x];
    for (ll nxt : v[x]) {
        if (!dfsn[nxt])ret = min(ret, dfs(nxt));
        else if (!fin[nxt])ret = min(ret, dfsn[nxt]);
    }
    if (ret == dfsn[x]) { //자신과 자신의 자손들 중 자신의 조상으로 가는 간선이 없을 경우
        vector<ll>curSCC;
        while (1) { //scc를 stack에서 빼주는 작업
            ll a = st.top();
            st.pop();
            curSCC.push_back(a);
            fin[a] = true;
            sn[a] = scc_count;
            if (a == x)break;
        }
        sort(curSCC.begin(), curSCC.end());
        SCC.push_back(curSCC);
        scc_count++;
    }
    return ret;
}

가장 핵심인 dfs코드입니다. 

3번째 줄을 보면 탐색한 노드들은 Stack에 넣어주는 것입니다. 그러다 scc가 완성되면 scc에 구성된 노드들을

stack에서 모두 pop 해줍니다.

4번째 줄을보면 변수 ret에 x번 노드의 방문순서를 넣어줍니다. 

 

5번째 줄을보면 현재 노드인 x와 연결된 모든 정점을 탐색할 것입니다.

 

6번째 if문을 보면  x와 연결된 노드가 탐색하지 않았다면 탐색하고 방문순서가 가장작은 ret값을 리턴해줍니다.

이는 7번째 줄과 연관됩니다.

 

7번째 줄을 보면 이미 6번째줄 if문을 무시하고 왔다는 의미입니다. 즉, x번 노드가 연결된 자손노드가 이미 탐색

되어 있다는 의미입니다. 결국 x번 노드의 조상으로가는 간선이 존재한다는 의미입니다.

만약 x번 노드의 조상노드가 아직 scc 추출이 되지않았다면 현재 x번 노드의 순서와 조상 노드 순서중에 작은 값을

ret에 저장합니다. 당연히 조상노드의 순서가 더 작을 것이므로 ret에는 조상노드가 들어갈 것입니다.

예를 들어 다음과 같은 그래프에서는 dfsn[4] = 1이고 dfsn[5] =2 인데 

5번 노드에서 조상노드인 4번 노드로 가는 간선이 있기 때문에 min(2, 1) 을 실행합니다.

즉 ret값에는 1이 들어가고 9번 if문에 조건에 맞지않아 23번째 줄 return으로 가게 됩니다.

재귀함수로 이루어져 있기 때문에 return 값은 x가 4인 dfs 6번째 줄에 돌아옵니다.

즉 ret값은 1이 됩니다.

 

9번째 줄 ~ 21번째줄은 scc를 추출한다는 의미입니다.

ret값이 dfsn[x]와 같다면 즉, 위의 for문을 계속 해서 돌아 현재 순서 값인 dfsn[x]가 그대로 유지 되었다면

스텍에 쌓여있던 scc들을 모두 pop 해주면서 scc를 저장하는 것입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<ll>v[10001]; //주어진 그래프 정보 저장
ll dfsn[10001];//방문 순서를 저장할 배열
ll scc_count; //scc의 갯수를 세는 변수
ll sn[10001]; //x번 정점이 몇번째 scc에 포함되어 있는지 알려주는 배열
vector<vector<ll>>SCC; //SCC를 벡터로 저장한 벡터의 벡터
stack<ll>st;
bool fin[10001];//x번쨰 정점이 scc추출이 끝났는지 확인
ll V, E, a, b,cnt;
ll dfs(ll x);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> V >> E;
    while (E--) {
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i <= V; i++)
        if (!dfsn[i])dfs(i); //방문하지 않은 정점들을 방문
    sort(SCC.begin(), SCC.end()); //문제에서 정렬된 상태로 출력해주기 때문
    cout << scc_count << '\n';
    for (auto cur : SCC) {
        for (auto c : cur)
            cout << c << ' ';
        cout << "-1" << '\n';
    }
    return 0;
}
ll dfs(ll x) { //x와 x의 자손들 중 올라갈 수 있는 최소의 dfsn값을 return(제일 위로 어디까지 갈 수 있는지)
    dfsn[x] = ++cnt; //방문순서를 계속해서 저장
    st.push(x);
    ll ret = dfsn[x];
    for (ll nxt : v[x]) {
        if (!dfsn[nxt])ret = min(ret, dfs(nxt));
        else if (!fin[nxt])ret = min(ret, dfsn[nxt]);
    }
    if (ret == dfsn[x]) { //자신과 자신의 자손들 중 자신의 조상으로 가는 간선이 없을 경우
        vector<ll>curSCC;
        while (1) { //scc를 stack에서 빼주는 작업
            ll a = st.top();
            st.pop();
            curSCC.push_back(a);
            fin[a] = true;
            sn[a] = scc_count;
            if (a == x)break;
        }
        sort(curSCC.begin(), curSCC.end());
        SCC.push_back(curSCC);
        scc_count++;
    }
    return ret;
}