백준 13232번: Domain clusters (C++)

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

13232번: Domain clusters

---

Solved By:  SCC(Kosaraju Algorithm)

 

 

아직은 SCC 알고리즘 중 Kosaraju Algorithm이 더 익숙해서 Kosaraju Algorithm을 이용하여 풀어보았습니다.

SCC 중에 사이즈가 제일 큰 값을 도출해내면 되는 문제였습니다. SCC 문제 중 크게 어려웠던 문제는 아니었던 거 같습니다.

Tarjan Algorithm을 이용하여 SCC 군집 노드끼리의 위상 정렬을 통해 풀 수 있는 문제들을 빨리 풀어봐야 할 거 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define MAX 5001
using namespace std;

int n, m;
vector<int> adj[MAX];
vector<int> radj[MAX];
bool visited[MAX];
stack<int> s;
int numSCC = 0;
vector<int> SCC[MAX];

void dfs(int node){
    if(visited[node]) return;
    visited[node] = 1;
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        if(!visited[next]) dfs(next);
    }
    
    s.push(node);
}

void rdfs(int node){
    if(visited[node]) return;
    visited[node] = 1;
    for(int i = 0; i < radj[node].size(); i++){
        int next = radj[node][i];
        if(!visited[next]) rdfs(next);
    }
    
    SCC[numSCC].push_back(node);
    return;
}

void makeSCC(){
    for(int i = 1; i <= n; i++) visited[i] = 0;
    while(!s.empty()){
        int now = s.top();
        s.pop();
        
        if(visited[now]) continue;
        
        rdfs(now);
        numSCC++;
    }
    return;
}

void kosaraju(){
    for(int i = 1; i <= n; i++){
        if(!visited[i]) dfs(i);
    }
    
    makeSCC();
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
    
    kosaraju();
    
    int result = 0;
    for(int i = 0; i < numSCC; i++){
        result = max(result, (int)SCC[i].size());
    }
    
    cout << result;
    return 0;
}