Cod sursa(job #3310546)

Utilizator tmi26Teodor Stupariu tmi26 Data 15 septembrie 2025 09:08:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int cst=500005;
vector<int> v[cst];
int f[cst],l[cst],is[cst],s[cst],cnt=0,sp=0;
int n,m;
vector<vector<int>>comp;
vector<int> curent;
void tarjan(int x)
{
    l[x]=++cnt;
    f[x]=l[x];
    s[++sp]=x;
    is[x]=1;
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i];
        if(f[y]==0)
        {
            tarjan(y);
            l[x]=min(l[x],l[y]);
        }
        else if(is[y])
        {
            l[x]=min(l[x],f[y]);
        }
    }
    if(l[x]==f[x])
    {
        curent.clear();
        int node=-1;
        while(node!=x)
        {
            node=s[sp--];
            is[node]=0;
            curent.push_back(node);
        }
        comp.push_back(curent);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]==0)
            tarjan(i);
    }
    fout<<comp.size()<<'\n';
    for(int i=0;i<comp.size();i++)
    {
        for(int j=0;j<comp[i].size();j++)
            fout<<comp[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}