Cod sursa(job #2865680)

Utilizator Mada_MeraMadalina Mera Mada_Mera Data 9 martie 2022 08:51:09
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,nr_elem,nrc,k,viz[50001],s[50001],T[2][50001],Start[50001],T2[2][50001],Start2[50001];
void df_suc(int nodstart)
{
    int man;
    viz[nodstart]=1;
    man=Start[nodstart];
    while(man)
    {
        if(viz[T[0][man]]==0)
            df_suc(T[0][man]);
        man=T[1][man];
    }
    s[++k]=nodstart;
}
void df_pred(int nodstart)
{
    int man;
    viz[nodstart]=nrc;
    man=Start2[nodstart];
    while(man)
    {
        if(viz[T2[0][man]]==0)
            df_pred(T2[0][man]);
        man=T2[1][man];
    }
}
void citire()
{
    int c,b,i;
    int k=0;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>c>>b;
        k++;
        T[0][k]=b;
        T[1][k]=Start[c];
        Start[c]=k;
        T2[0][k]=c;
        T2[1][k]=Start2[b];
        Start2[b]=k;
    }
}
void initializare_viz()
{
    for(int i=1;i<=n;i++)
        viz[i]=0;
}
int main()
{
    int i,j;
    citire();
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            df_suc(i);
    initializare_viz();
    for(i=k;i>=1;i--)
    {
        if(viz[s[i]]==0)
        {
            nrc++;
            df_pred(s[i]);
        }
    }
    g<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(j=1;j<=n;j++)
            if(viz[j]==i)
                g<<j<<" ";
        g<<'\n';
    }
    return 0;
}