Cod sursa(job #3133906)

Utilizator lucidanescu28Danescu Lucian lucidanescu28 Data 27 mai 2023 13:55:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define PRINT_VECTOR(V) for (int I = 0; I < V.size(); I++) fout << V[I] << " "; fout << "\n";

const int DIM = 1e5 + 1;

vector <int> adj[DIM];
int ids[DIM], low[DIM];
bool onStack[DIM];
stack<int> nodeStack;
vector<vector<int>> scc;
int id;

void dfs(int v);

void tarjanSCC(int V) {
    for (int i = 1; i <= V; ++i) { // iterate from 1 to V
        if (ids[i] == -1) {
            dfs(i);
        }
    }
}

void dfs(int v) {
    ids[v] = low[v] = id++;
    nodeStack.push(v);
    onStack[v] = true;

    for (int neighbor : adj[v]) {
        if (ids[neighbor] == -1) {
            dfs(neighbor);
        }
        if (onStack[neighbor]) {
            low[v] = min(low[v], low[neighbor]);
        }
    }

    // If v is a root node, pop the stack and print the SCC
    if (ids[v] == low[v]) {
        vector<int> temp;

        while (!nodeStack.empty()) {
            int node = nodeStack.top();
            nodeStack.pop();
            onStack[node] = false;
            
            temp.push_back(node);

            if (node == v) {
                break;
            }
        }

        scc.push_back(temp);
    }
}

int main() {
    int V, E;
    fin >> V >> E;

    for (int i = 0; i < DIM; ++i) {
        ids[i] = -1;
        low[i] = -1;
    }

    while (E--) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }

    tarjanSCC(V);

    fout << scc.size() << "\n";

    for (auto s : scc) {
        PRINT_VECTOR(s);
    }
        

    return 0;
}