Cod sursa(job #3243542)

Utilizator MikeStrikeAgache Mihai MikeStrike Data 19 septembrie 2024 12:50:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<vector<int>> G;
vector<int> num, lowest;
vector<bool> onStack;
stack<int> s;
vector<vector<int>> sccs;
int index = 0;

void tarjanDFS(int v) {
    num[v] = lowest[v] = index++;
    s.push(v);
    onStack[v] = true;

    for (int u : G[v]) {
        if (num[u] == -1) {
            tarjanDFS(u);
            lowest[v] = min(lowest[v], lowest[u]);
        } else if (onStack[u]) {
            lowest[v] = min(lowest[v], num[u]);
        }
    }

    if (lowest[v] == num[v]) {
        vector<int> component;
        int w;
        do {
            w = s.top();
            s.pop();
            onStack[w] = false;
            component.push_back(w);
        } while (w != v);
        sccs.push_back(component);
    }
}

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

    int N, M;
    fin >> N >> M;

    G.resize(N);
    num.assign(N, -1);
    lowest.assign(N, -1);
    onStack.assign(N, false);

    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        --x; --y; 
        G[x].push_back(y);
    }

    for (int v = 0; v < N; ++v) {
        if (num[v] == -1) {
            tarjanDFS(v);
        }
    }

    // Write output
    fout << sccs.size() << endl;
    for (const vector<int>& scc : sccs) {
        for (int v : scc) {
            fout << v + 1 << " "; 
        }
        fout << endl;
    }

  

    return 0;
}