Cod sursa(job #3350970)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 15 aprilie 2026 11:51:38
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX=100007;
int n,m;
int x,y;
vector<int> adj[NMAX];
stack<int> stec;
int lvl[NMAX];
int lowlink[NMAX];
int b[NMAX];
int instec[NMAX];
int timp=0;
vector<vector<int>> fin;
vector<int> ras;
void dfs(int nod)
{
    lowlink[nod]=lvl[nod];
    stec.push(nod);
    instec[nod]=1;
    for(auto w:adj[nod])
    {
        if(b[w]==0)
        {
            b[w]=1;
            timp++;
            lvl[w]=timp;
            dfs(w);
            if(lowlink[w]<lowlink[nod])
            {
                lowlink[nod]=lowlink[w];
            }
        }
        else if(instec[w]==1)
        {
            if(lowlink[w]<lowlink[nod])
            {
                lowlink[nod]=lowlink[w];
            }
        }
    }
    if(lowlink[nod]>=lvl[nod])
    {
        ras.clear();
        while(stec.top()!=nod)
        {
            ras.push_back(stec.top());
            instec[stec.top()]=0;
            stec.pop();
        }
        ras.push_back(stec.top());
        instec[stec.top()]=0;
        stec.pop();
        fin.push_back(ras);
    }
    return;
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        adj[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==0)
        {
            lvl[i]=timp;
            timp++;
            b[i];
            dfs(i);
        }
    }
    out<<fin.size()<<"\n";
    for(auto vec:fin)
    {
        for(auto nod:vec)
        {
            out<<nod<<" ";
        }
        out<<"\n";
    }
}