SCC: Kosaraju's Algorithm

[illuminoplanet]

No description provided.

[dotoleeoak]

#include <bits/stdc++.h>
using namespace std;

int v, e;
vector<vector<int>> graph, graph_r;
set<set<int>> scc;
bool visit[10001];
stack<int> s;

void dfs(int u) {
    visit[u] = true;
    for (auto v : graph[u])
        if (!visit[v]) dfs(v);
    s.push(u);
}

void dfs_r(int u, set<int> &s) {
    visit[u] = true;
    s.insert(u);
    for (auto v : graph_r[u])
        if (!visit[v]) dfs_r(v, s);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> v >> e;
    graph.resize(v + 1);
    graph_r.resize(v + 1);
    while (e--) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph_r[v].push_back(u);
    }
    for (int i = 1; i <= v; i++)
        if (!visit[i]) dfs(i);
    memset(visit, false, sizeof(visit));
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!visit[cur]) {
            set<int> temp;
            dfs_r(cur, temp);
            scc.insert(temp);
        }
    }
    cout << scc.size() << '\n';
    for (auto i : scc) {
        for (auto j : i) cout << j << ' ';
        cout << "-1\n";
    }
}

[illuminoplanet]

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<vector<int>> edge, inverse_edge;
int v, e;

void dfs(vector<bool>& check, stack<int>& visit, int curr)
{
    check[curr] = true;
    for (int next : edge[curr])
    {
        if (check[next]) continue;
        dfs(check, visit, next);
    }
    visit.push(curr);
}

set<set<int>> kosaraju(void)
{
    vector<bool> check(v+1, false);
    stack<int> visit;
    for (int i = 1; i <= v; i++)
    {
        if (check[i]) continue;
        dfs(check, visit, i);
    }

    check = vector<bool>(v+1, false);
    set<set<int>> ret;
    while (!visit.empty())
    {
        int node = visit.top(); visit.pop();
        if (check[node]) continue;

        stack<int> sk; sk.push(node);
        set<int> se;
        while (!sk.empty())
        {
            int curr = sk.top(); sk.pop();
            check[curr] = true;
            se.insert(curr);
            for (int next : inverse_edge[curr])
            {
                if (check[next]) continue;
                sk.push(next);
            }
        }
        ret.insert(se);
    }
    return ret;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> v >> e;
    edge.resize(v+1); inverse_edge.resize(v+1);
    for (int i = 0; i < e; i++)
    {
        int a, b; cin >> a >> b;
        edge[a].push_back(b);
        inverse_edge[b].push_back(a);
    }
    set<set<int>> scc = kosaraju();

    return 0;
}

[dotoleeoak]

풀리퀘를 해

[dotoleeoak]

@illuminoplanet 난 그냥 참고하라고 올린거임

[illuminoplanet]

@dotoleeoak 난 자랑하려고 올린거야

[dotoleeoak]

@illuminoplanet ;;

[dotoleeoak]

return type 바꾸기 (vector<vector<int>> 쓰지 말기)