Cod sursa(job #2715171)

Utilizator marius004scarlat marius marius004 Data 3 martie 2021 09:26:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

using namespace std;

ifstream  f("ctc.in");
ofstream g("ctc.out");

const int NMAX = 100001;

int N, M, level[NMAX], low[NMAX], cnt, scc_cnt;
vector < int > G[NMAX];
bitset < NMAX > inStack, beenThere;
stack < int > nodes;
vector < int > scc[NMAX];

void dfs(int node) {

    cnt++;
    level[node] = low[node] = cnt;
    inStack[node] = 1;
    nodes.push(node);
    beenThere[node] = 1;

    for(auto& it : G[node]) {
        if(level[it] == 0) { // daca nu a fost vizitat fac un dfs
            dfs(it);
            low[node] = min(low[node], low[it]);
        } else if(inStack[it] == 1)
            low[node] = min(low[node], low[it]);
    }

    if(level[node] == low[node]) {

        int x{};

        scc_cnt++;

        do {
            x = nodes.top();
            nodes.pop();
            inStack[x] = 0;
            scc[scc_cnt].push_back(x);
        } while(x != node);

    }
}

int main() {

    f >> N >> M;

    for(;M--;) {

        int x, y;
        f >> x >> y;

        G[x].push_back(y);
    }

    for(int i = 1;i <= N;++i)
        if(!beenThere[i])
            dfs(i);

   g << scc_cnt << '\n';

   for(int i = 1;i <= scc_cnt;++i, g << '\n')
       for(auto& it : scc[i])
           g << it << ' ';

    return 0;
}