Strongly Connected Component - 2150

//백준 SCC - 2150
 
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
 
int V, E;
vector<vector<int>> adj;
vector<int> discovered;
vector<int> sccId;
priority_queue<pair<int, vector<int>>> pq;
stack<int> st;
int sccCounter = 0, counter = 0;
 
bool operator<(pair<int, vector<int>> &p1, pair<int, vector<int>> &p2)
{
    return p1.first < p2.first;
}
 
int scc(int here)
{
    int ret = discovered[here] = counter++;
    int there;
    st.push(here);
    for (int i = 0; i < adj[here].size(); i++)
    {
        there = adj[here][i];
        if (discovered[there] == -1)
            ret = min(ret, scc(there));
        else if (sccId[there] == -1)
            ret = min(ret, discovered[there]);
    }
 
    if (ret == discovered[here])
    {
        vector<int> v;
        while(true)
        {
            int t = st.top(); st.pop();
            sccId[t] = sccCounter;
            v.push_back(t);
            if(t == here)
                break;
        }
        ++sccCounter;
        sort(v.begin(), v.end());
        pq.push(make_pair(-1*v[0], v));
    }
    return ret;
}
 
void tarjanScc()
{
    for (int i = 1; i <= V; i++)
        if (discovered[i] == -1)
            scc(i);
}
 
int main()
{
    cin >> V >> E;
    adj = vector<vector<int>>(V + 1);
    sccId = discovered = vector<int>(V + 1, -1);
    st = stack<int>();
    int x, y;
    for (int i = 0; i < E; i++)
    {
        cin >> x >> y;
        adj[x].push_back(y);
    }
 
    tarjanScc();
    cout << sccCounter << endl;
    while (!pq.empty())
    {
        vector<int> v = pq.top().second;
        pq.pop();
        for(int i =0 ; i<v.size(); i++)
            cout << v[i] << " ";
        cout << "-1" << endl;
    }
}

 

 

 

 

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

2150번: Strongly Connected Component

 

 

 

 

Strongly Connected Component

SCC문제 tarjan's SCC algorithm을 이용했습니다.