Cod sursa(job #2928710)

Utilizator PepiNedelcu Radu Pepi Data 23 octombrie 2022 18:25:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

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


int n, m;

int onStack[100001], ids[100001], low[100001], idx;
stack <int> S;
vector <int> G[100001];

vector <vector <int>> Ans;

void strongConnect(int curent) {
    ids[curent] = idx;
    low[curent] = idx;
    idx++;
    S.push(curent);
    onStack[curent] = 1;
    for (int node : G[curent]) {
        if (ids[node] == 0) {
            strongConnect(node);
            low[curent] = min(low[curent], low[node]);
        }
        else if (onStack[node]) {
            low[curent] = min(low[curent], ids[node]);
        }
    }
    if (ids[curent] == low[curent]) {
        vector <int> scc;
        int node;
        do {
            node = S.top();
            S.pop();
            onStack[node] = 0;
            scc.push_back(node);
        } while (curent != node);
        Ans.push_back(scc);
    }
}


int main() {

    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        fin >> u >> v;
        G[u].push_back(v);
    }

    idx = 1;
    for (int i = 1; i <= n; i++) {
        if (ids[i] == 0) {
            strongConnect(i);
        }
    }

    fout << Ans.size() << "\n";
    for (int i = 0; i < Ans.size(); i++) {
        for (int j = 0; j < Ans[i].size(); j++) {
            fout << Ans[i][j] << " ";
        }
        fout << "\n";
    }
    return 0;
}