Cod sursa(job #2939838)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 14 noiembrie 2022 10:54:22
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")

using namespace std;

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

const int MAX_N = 100005;
int n, m, outcnt;
vector <int> out[MAX_N], v[MAX_N];
bitset <MAX_N> ctc, viz;
stack <int> stk;

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

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

    if(level[nod] == init[nod]){
        outcnt++;
        while(stk.top() != nod){
            out[outcnt].emplace_back(stk.top());
            stk.pop();
        }
        out[outcnt].emplace_back(stk.top());
        stk.pop();
    }
}



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

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

    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 : out[i])
            fout<<nod<<" ";
    return 0;
}