Cod sursa(job #2539971)

Utilizator cezarus30cezarus30 cezarus30 Data 6 februarie 2020 16:31:56
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>

#include <fstream>

using namespace std;

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

const int N= 100001;
const int M= 200001;

int stiva[N],cnt,stiva_inv[N];
int lst[N],vf[2*M] , urm[2*M], n , nr ;
int lst_inv[N], vf_inv[2*M],urm_inv[2*M],viz_inv[N];
int ans[2*N+1],anspos;
bool viz[N];

void dfs_top(int x)
{
    viz[x]=true;
    int y;
    for(int p=lst[x]; p!=0 ; p=urm[p])
    {
        y=vf[p];
        if(!viz[y])
            dfs_top(y);
    }
    stiva[++cnt]=x;
}


void dfs_top_inv(int x)
{
    viz_inv[x]=true;
    ans[anspos++]=x;
    int y;
    for(int p=lst_inv[x];p!=0;p=urm_inv[p])
    {
        y=vf_inv[p];
        if( !viz_inv[y])
            dfs_top_inv(y);
    }
    stiva_inv[++cnt]=x;
}


void adauga (int x, int y )
{
    ++nr;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    vf_inv[nr]=x;
    urm_inv[nr]=lst_inv[y];
    lst_inv[y]=nr;
}


int main()
{
    int n,m,x,y;
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        in>>x>>y;
        adauga(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
            dfs_top(i);
    }
    cnt=0;
    int nrof=0;
    for(int i=n;i>0;i--)
    {
        if(!viz_inv[stiva[i]])
        {
            dfs_top_inv(stiva[i]);
            ans[anspos]=-1;
            ++nrof;
        }
    }
    out<<nrof<<'\n';
    for(int i=0;i< anspos;i++)
    {
        if(ans[i] == -1)
            out<<'\n';
        else
            out<<ans[i]<<" ";
    }
    return 0;
}