Cod sursa(job #2518382)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 5 ianuarie 2020 17:09:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define Dim 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

vector < int > V[Dim],VT[Dim],A[Dim];

int N,M,x,y,post[Dim],cnt,viz[Dim],ans;

void DFS(int nod)
{
    viz[nod]=1;
    for(unsigned int i=0;i<V[nod].size();i++)
    {
        int vecin=V[nod][i];
        if(!viz[vecin]) DFS(vecin);
    }
    viz[nod]=2;
    post[++cnt]=nod;
}

void DFST(int nod)
{
    viz[nod]=1;
    A[ans].push_back(nod);
    for(unsigned int i=0;i<VT[nod].size();i++)
    {
        int vecin=VT[nod][i];
        if(!viz[vecin]) DFST(vecin);
    }
    viz[nod]=2;
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>x>>y;
        V[x].push_back(y);
        VT[y].push_back(x);
    }

    for(int i=1;i<=N;i++)
    if(!viz[i]) DFS(i);

    for(int i=1;i<=N;i++) viz[i]=0;

    for(int i=cnt;i>=1;i--)
    if( !viz[ post[ i ] ] )
    {
        ans++;
        DFST(post[i]);
    }

    g<<ans<<'\n';
    for(int i=1;i<=ans;i++)
    {
        for(int j=0;j<A[i].size();j++) g<<A[i][j]<<" ";
        g<<'\n';
    }

    return 0;
}