Cod sursa(job #1969516)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 18 aprilie 2017 15:04:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#define NMax 100005
using namespace std;

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

vector<int> G[NMax], Gt[NMax], ctc[NMax];

int N, M, i, j, a, b, nrsol, st[NMax], viz[NMax];

void DFS (int x)
{
    viz[x]=1;
    for(int i=0; i<G[x].size(); i++)
        if(!viz[G[x][i]])
            DFS(G[x][i]);

    st[++st[0]]=x;
}
void DFST (int x)
{
    viz[x]=1;
    for(int i=0; i<Gt[x].size(); i++)
        if(!viz[Gt[x][i]])
            DFST(Gt[x][i]);

    ctc[nrsol].pb(x);
}
int main()
{
    f>>N>>M;
    for(i=1; i<=M; i++)
    {
        f>>a>>b;
        G[a].pb(b);
        Gt[b].pb(a);
    }

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

    memset(viz, 0, sizeof(viz));

    for(i=N; i>=1; i--)
        if(!viz[st[i]])
        {
            ++nrsol;
            DFST(st[i]);
        }
    g<<nrsol<<'\n';
    for(i=1; i<=nrsol; i++)
    {
        for(j=0; j<ctc[i].size(); j++)
            g<<ctc[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}