Cod sursa(job #3277992)

Utilizator sheesh07Andrei Giurgiu sheesh07 Data 18 februarie 2025 13:48:35
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>

using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, m, x, y, t[2][501000], start[501000], k, c[501000], v[501000], dr, tt[2][501000], startt[501000], kt, vt[501000], nr, af[501000], p;

void liste(int i,int j)
{
    k++;
    t[0][k]=j;
    t[1][k]=start[i];
    start[i]=k;
}

void listet(int i,int j)
{
    kt++;
    tt[0][k]=i;
    tt[1][k]=start[j];
    startt[j]=kt;
}

int dfs(int s)
{
    int man=start[s];
    v[s]=1;
    while(man)
    {
        if(v[t[0][man]]==0) dfs(t[0][man]);
        man=t[1][man];
    }
    c[++dr]=s;
}

int dfst(int s)
{
    int man=startt[s];
    vt[s]=1;
    af[++p]=s;
    while(man)
    {
        if(vt[tt[0][man]]==0) dfst(tt[0][man]);
        man=tt[1][man];
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        liste(x,y);
        listet(x,y);
    }
    for(int i=1;i<=n;i++) if(v[i]==0) dfs(i);
    for(int i=dr;i>=1;i--)
    {
        v[i]=0;
        if(vt[c[i]]==0)
        {
            nr++;
            dfst(c[i]);
            af[++p]=-1;
        }
    }
    cout<<nr<<'\n';
    for(int i=1;i<=p;i++)
    {
        if(af[i]!=-1) cout<<af[i]<<' ';
        else cout<<'\n';
    }
    return 0;
}