Cod sursa(job #3301925)

Utilizator Anul2024Anul2024 Anul2024 Data 1 iulie 2025 11:48:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#define dim 100000
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n,m,k,nr,low[dim+1],s[dim+1];
vector <int> v[dim+1],ctc;
vector <vector <int>> sol;
bool vis[dim+1],stk[dim+1];
void read ()
{
    int x,y;
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back (y);
    }
}
void dfs (int nod)
{
    nr++;
    int nrr=nr;
    low[nod]=nr;
    vis[nod]=stk[nod]=1;
    s[++k]=nod;
    for (int i=0; i<(int)v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (!vis[vecin])
            dfs (vecin);
        if (stk[vecin])
            low[nod]=min (low[nod],low[vecin]);
    }
    if (low[nod]==nrr)
    {
        ctc.clear ();
        while (ctc.empty ()||ctc.back ()!=nod)
        {
            stk[s[k]]=0;
            ctc.push_back (s[k--]);
        }
        sol.push_back (ctc);
    }
}
void print ()
{
    fout<<(int)sol.size ()<<"\n";
    for (int i=0; i<(int)sol.size (); i++)
    {
        for (int j=0; j<(int)sol[i].size (); j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
}
int main()
{
    read ();
    for (int i=1; i<=n; i++)
    {
        if (!vis[i])
            dfs (i);
    }
    print ();
    return 0;
}