[C++] 2150번 Strongly Connected Component - 그래프 이론, 강한 연결 요소

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

#define MAX_V 10001

using namespace std;

int V, E;  //정점의 개수 V, 간선의 개수 E
int vs[MAX_V], scc[MAX_V];  //visited 방문했는가? 이미 scc에 들어갔는가?
int cnt;  //bfs로 탐색된 순서
stack<int> st;
vector<vector<int>> res, gr;  //result, graph

bool cmp(vector<int> x, vector<int> y)  //벡터 정렬
{
    return x[0] < y[0];
}

void input()
{
    cin >> V >> E;
    gr.resize(V+1);
    for(int i=0; i<E; i++) {
        int a, b; cin >> a >> b;
        gr[a].push_back(b);
    }
}

int dfs(int no)  //타잔 알고리즘
{
    st.push(no);
    vs[no] = cnt++;  //탐색된 순서 저장
    
    int pa = vs[no];  //parent, 처음 방문되었으면 부모는 자신
    
    for(int i=0; i<gr[no].size(); i++) {
        int next = gr[no][i];
        if(vs[next]==-1) pa = min(pa, dfs(next));
        else if(scc[next]==-1) pa = min(pa, vs[next]);
    }
    if(pa == vs[no]) {
        vector<int> tmp;
        while(1) {
            int here = st.top(); st.pop();
            scc[here]=1;
            tmp.push_back(here);
            if(here==no) break;
        }
        sort(tmp.begin(), tmp.end());
        res.push_back(tmp);
    }
    return pa;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    fill(vs, vs+MAX_V, -1); fill(scc, scc+MAX_V, -1);  //초기화
    
    for(int i=1; i<=V; i++)
        if(vs[i]==-1) dfs(i);
    
    sort(res.begin(), res.end(), cmp);  //오름차순 정렬
    cout << res.size() << '\n';
    for(int i=0; i<res.size(); i++) {
        for(int j=0; j<res[i].size(); j++)
            cout << res[i][j] << ' ';
        cout << -1 << '\n';
    }
    
    return 0;
}

타잔 알고리즘으로 풀었다. 사실 강한 연결 요소는 처음 보는 거라서 다른 블로그를 보면서 공부했다.

 

요즘 모르는 알고리즘들이 계속 나오고 있다. class문제가 아마 이 티어에서 꼭 봐야 되는 알고리즘들만 묶어서 주는 것 같다. 그래서 아마 똑같은 알고리즘을 쓰는 문제가 거의 없는 게 아닐까?

 

처음으로 알게 된 사실이 있는데 .size()는 unsigned int형을 반환한다는 것이다. 즉 여기서 -1을 하게 되면 -1이 아닌 unsigned int 최대 숫자가 된다. ㄷㄷ 참고한 사이트는 아래에 있다.

 

 

 

<SCC 알고리즘>

https://ip99202.github.io/posts/SCC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

SCC 알고리즘

 

<C++ fill() 함수>

https://twpower.github.io/121-usage-of-fill-function

[C++] fill 함수 사용하기

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.