Cod sursa(job #3346343)

Utilizator Ianis_PIMDuca Ianis Ianis_PIM Data 13 martie 2026 11:48:30
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>>adj;
vector<bool>V;
vector<int>nivel;
vector<int>nma;
stack<int>S;
vector<bool>inS;
vector<vector<int>>R;
int n,m,cnt=0,c;
void DFS(int k)
{
    c++;
    V[k]=true;
    S.push(k);
    nivel[k]=c;
    inS[k]=true;
    nma[k]=c;
    for(auto x:adj[k])
        if(!V[x])
        {
            DFS(x);
            nma[k]=min(nma[k],nma[x]);
        }
        else if(inS[x])
            nma[k]=min(nma[k],nivel[x]);
    if(nivel[k]==nma[k])
    {
        R.push_back(vector<int>());
        while(S.top()!=k)
        {
            inS[S.top()]=false;
            R[cnt].push_back(S.top());
            S.pop();
        }
        inS[k]=false;
        R[cnt].push_back(k);
        S.pop();
        cnt++;
    }
}
int main()
{
    int x,y;
    fin>>n>>m;
    adj.resize(n+1);
    V.resize(n+1,0);
    nivel.resize(n+1);
    nma.resize(n+1);
    inS.resize(n+1,0);
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        adj[x].push_back(y);
    }
    for(int i=1; i<=n; i++)
        if(!V[i])
            DFS(i);
    fout<<cnt<<endl;
    for(int i=0; i<cnt; i++,fout<<endl)
        for(int j:R[i])
            fout<<j<<" ";
    return 0;
}