Cod sursa(job #3278005)

Utilizator Codrut_NeagNeag Codrut Serban Codrut_Neag Data 18 februarie 2025 14:32:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>

using namespace std;

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

int n, m, t[2][500100], start[500100], gt[2][500100], gstart[500100], timp[500100], nr, ans[500100], a;
bool viz[500100], vizt[500100];
void citire()
{
    int x, y;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        t[0][i]=y;
        t[1][i]=start[x];
        start[x]=i;
        gt[0][i]=x;
        gt[1][i]=gstart[y];
        gstart[y]=i;
    }
}

void dfst(int x)
{
    int man=gstart[x];
    vizt[x]=1;
    while(man)
    {
        if(vizt[gt[0][man]]==0)
            dfst(gt[0][man]);
        man=gt[1][man];
    }
    timp[++nr]=x;
}

void dfs(int x)
{
    int man=start[x];
    viz[x]=1;
    while(man)
    {
        if(viz[t[0][man]]==0)
            dfs(t[0][man]);
        man=t[1][man];
    }
    ans[++a]=x;
}

int main()
{
    int conex=0;
    citire();
    for(int i=1; i<=n; i++)
        if(vizt[i]==0)
            dfst(i);
    for(int i=nr; i>0; i--)
    {
        if(viz[timp[i]]==0)
        {
            conex++;
            dfs(timp[i]);
            ans[++a]=-1;
        }
    }
    out<<conex<<'\n';
    for(int i=1; i<=a; i++)
    {
        if(ans[i]!=-1)
            out<<ans[i]<<" ";
        else out<<'\n';
    }
    return 0;
}