Cod sursa(job #2898127)

Utilizator LIR16LazarIonutRadu LIR16 Data 6 mai 2022 01:26:20
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <vector>
#include <stack>
#define NMAX 100005

using namespace std;

stack<int> sk;
int viz[NMAX];
vector<int> adj[NMAX];
vector<int> rev_adj[NMAX];
int N, M;

void DFS_K(int node)
{
    viz[node] = 1;

    for (int i = 0; i < adj[node].size(); i++) {
        if (!viz[adj[node][i]])
            DFS_K(adj[node][i]);
    }
    sk.push(node);
}

int ans;
vector<int> comps;
void DFS_K2(int node)
{
    viz[node] = 1;
    comps.push_back(node);

    for (int i = 0; i < rev_adj[node].size(); i++) {
        if (!viz[rev_adj[node][i]])
            DFS_K2(rev_adj[node][i]);
    }
}

void Kosaraju()
{
    for (int i = 1; i <= N; i++)
        viz[i] = 0;

    // DFS through the graph and add to a stack nodes when they don't have any unvisited neighbours.
    for (int i = 1; i <= N; i++)
        if (!viz[i])
            DFS_K(i);

    for (int i = 1; i <= N; i++)
        viz[i] = 0;

    // DFS through the transpose matrix from the nodes in the stack.
    while (!sk.empty())
    {
        if (!viz[sk.top()]) {
            DFS_K2(sk.top());
            comps.push_back(-1);
            ans++;
        }
        sk.pop();
    }

    cout << ans << '\n';
    for (int j = 0; j < comps.size(); j++)
        if (comps[j] != -1)
            cout << comps[j] << " ";
        else
            cout << '\n';
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    cin >> N >> M;
    int node1, node2;
    for (int i = 1; i <= M; i++) {
        cin >> node1 >> node2;

        adj[node1].push_back(node2);
        rev_adj[node2].push_back(node1);
    }

    Kosaraju();
    
    return 0;
}