Cod sursa(job #2931219)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 30 octombrie 2022 17:49:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_N = 100005;
const int MAX_M = 200005;
int n, m, outcnt;
vector <int> edge[MAX_N], output[MAX_N];
bitset <MAX_N> viz, ctc;

stack <int> stk;
static inline void add_ctc(){
    ctc[stk.top()] = true;
    output[outcnt].emplace_back(stk.top());
    stk.pop();
}

int level[MAX_N], init[MAX_N], lvl;
inline void tarjan(int crt){
    viz[crt] = true;
    stk.push(crt);
    level[crt] = init[crt] = ++lvl;

    for(auto nxt : edge[crt])
        if(!ctc[nxt]){
            if(!viz[nxt]){
                tarjan(nxt);
                level[crt] = min(level[crt], level[nxt]);
            }else{
                level[crt] = min(level[crt], init[nxt]);
            }
        }

    if(level[crt] == init[crt]){
        outcnt++;
        while(stk.top() != crt)
            add_ctc();
        add_ctc();
    }
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

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

   for(int i=1; i<=n; i++)
        if(!viz[i])
            tarjan(i);

    fout<<outcnt<<"\n";
    for(int i=1; i<=outcnt; i++, fout<<"\n")
        for(auto nod : output[i])
            fout<<nod<<" ";
    return 0;
}