Cod sursa(job #3194197)

Utilizator lucriLuchian Cristian lucri Data 17 ianuarie 2024 11:31:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
std::ifstream cin("ctc.in");
std::ofstream cout("ctc.out");
int n,m,x,y;
bool e[100010];
int low[100010],nr,val[100010];
std::vector<std::vector<int>>a;
std::stack<std::vector<int>>sv;
std::stack<int>s;
std::vector<int>zero;
void pleaca(int nod)
{
    low[nod]=val[nod]=++nr;
    e[nod]=true;
    s.push(nod);
    for(auto x:a[nod])
    {
        if(e[x]==true)
            low[nod]=std::min(low[nod],val[x]);
        else if(val[x]==0)
        {
            pleaca(x);
            low[nod]=std::min(low[nod],low[x]);
        }
    }
    if(val[nod]==low[nod])
    {
        sv.push(zero);
        while(s.top()!=nod)
        {
            sv.top().push_back(s.top());
            e[s.top()]=false;
            s.pop();
        }
        sv.top().push_back(s.top());
        e[s.top()]=false;
        s.pop();
    }
}
int main()
{
    cin>>n>>m;
    a.resize(n+5);
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        a[x].push_back(y);
    }
    for(int i=1;i<=n;++i)
        if(val[i]==0)
            pleaca(i);
    cout<<sv.size()<<'\n';
    while(!sv.empty())
    {
        for(auto x:sv.top())
            cout<<x<<' ';
        cout<<'\n';
        sv.pop();
    }
    return 0;
}