Cod sursa(job #2530863)

Utilizator rares9991Matisan Rares-Stefan rares9991 Data 25 ianuarie 2020 13:24:31
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

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

const int N=100001;
const int M=2*N;

int lst[N], vf[2*M], urm[2*M], lst_inv[N], vf_inv[2*M], urm_inv[2*M], sorttop[N], ctc[2*M], k[N];
int nr, ct, cnt, ans, alt;

int fr[N];

bool viz[N];

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;
}

void dfs1(int x)
{
    viz[x]=true;
    for(int p=lst[x]; p!=0; p=urm[p])
    {
        int y=vf[p];
        if(!viz[y])
            dfs1(y);
    }
    sorttop[++nr]=x;
}

void dfs2(int x)
{
    viz[x]=true;
    for(int p=lst_inv[x]; p!=0; p=urm_inv[p])
    {
        int y=vf_inv[p];
        if(!viz[y])
        {
            fr[x]=fr[x]+1;
            cnt++;
            ctc[cnt]=y;
            dfs2(y);
        }
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;
        adauga(x,y);
    }
    nr=0;
    for(int i=1; i<=n; i++)
        if(!viz[i])
        {
            dfs1(i);
            alt++;
        }
    if(alt!=1)
        fout<<0;
    else
    {
        nr=0;
        for(int i=1; i<=n; i++)
            viz[i]=false;
        for(int i=n; i>=1; i--)
        {
            if(!viz[sorttop[i]])
            {
                ct++;
                cnt++;
                ctc[cnt]=sorttop[i];
                dfs2(sorttop[i]);
                cnt++;
                ctc[cnt]=-1;
            }
        }
        int s=0;
        nr=0;
        for(int i=1; i<=cnt; i++)
        {
            if(ctc[i]==-1)
            {
                nr++;
                k[nr]=s;
                s=0;
            }
            else
                s+=fr[ctc[i]];
        }
        for(int i=1; i<=nr; i++)
            if(k[i]!=0)
            {
                ct=0;
                for(int j=1; j<=cnt; j++)
                {
                    if(ctc[j]==-1)
                        ct++;
                    if(ct==i)
                    {
                        j--;
                        int cop=j;
                        int u=0;
                        while(ctc[cop]!=-1 and cop>=1)
                        {
                            u++;
                            cop--;
                        }
                        cop++;
                        fout<<u<<"\n";
                        while(ctc[cop]!=-1 and cop<=n)
                            fout<<ctc[cop]<<"\n", cop++;
                        return 0;
                    }
                }
            }
    }
    return 0;
}