Cod sursa(job #3286376)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 14 martie 2025 09:35:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

#define DIM 100000

using namespace std;

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

int n,m;
int x,y;

vector<int>  L[DIM+5];

int compk = 0;
vector<int> comp[DIM+5];

bool u[DIM+5];
bool in[DIM+5];

int niv[DIM+5];
int nma[DIM+5];

int k = 0;

stack <int> s;
void dfs(int nod){
    //cout<<nod<<'\n';

    u[nod] = 1;

    k++;
    niv[nod] = k;
    nma[nod] = k;

    in[nod] = 1;
    s.push(nod);

    for(auto vec:L[nod]){

        if(!u[vec]){
            dfs(vec);
            nma[nod] = min(nma[nod],nma[vec]);
        }else if(in[vec]){
            nma[nod] = min(nma[nod],niv[vec]);
        }

    }

    if(niv[nod] == nma[nod]){

        compk++;

        while(s.top() != nod){

            comp[compk].push_back(s.top());
            in[s.top()] = 0;
            s.pop();

        }

        comp[compk].push_back(s.top());
        in[s.top()] = 0;
        s.pop();

    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y;
        L[x].push_back(y);
    }

    for(int i=1;i<=n;i++){
        if(!u[i]){
            dfs(i);
        }
    }

    g<<compk<<'\n';
    for(int i=1;i<=compk;i++){
        for(auto j:comp[i]){
            g<<j<<" ";
        }
        g<<'\n';
    }


    return 0;
}