Cod sursa(job #2254674)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 5 octombrie 2018 18:59:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define Dim 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,x,y,POST[Dim],cnt,ans;
bool viz[Dim],vizT[Dim];
vector < int > Vf[Dim],VT[Dim],CTC[Dim];

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

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

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

int main()
{
    Citire();
    for(int i=1;i<=N;i++)
    if(!viz[i])
    {
        viz[i]=1;
        DFS(i);
    }
    for(int i=cnt;i>=1;i--)
    if(!vizT[POST[i]])
    {
        ans++;
        vizT[POST[i]]=1;
        DFST(POST[i]);
    }
    g<<ans;
    for(int i=1;i<=ans;i++)
    {
        g<<'\n';
        for(unsigned int j=0;j<CTC[i].size();j++)
        g<<CTC[i][j]<<" ";
    }
    return 0;
}