Cod sursa(job #2582064)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 16 martie 2020 12:48:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <stack>
#define dim 100005

using namespace std;

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

vector <int> G[dim];
vector <int> GT[dim];///GRAF TRANSPUS
stack <int> postordine;
vector <int> Ctc[dim];
int viz[dim];
int n,m,X,NrCtc;

void citire()
{
    fin>>n>>m;
    for(int i=0,x,y; i<m; i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void DFS(int X)
{
    viz[X]=1;
    int N=G[X].size();
    for(int i=0; i<N; i++)
    {
        int vecin=G[X][i];
        if(!viz[vecin])
            DFS(vecin);
    }
    postordine.push(X);
}

void DFST(int X)
{
    viz[X]=2;
    Ctc[NrCtc].push_back(X);
    int N=GT[X].size();
    for(int i=0; i<N; i++)
    {
        int vecin=GT[X][i];
        if(viz[vecin]==1)
            DFST(vecin);
    }
}

void afisare()
{
    fout<<NrCtc<<'\n';;
    for(int i=1; i<=NrCtc; i++)
    {
        int N=Ctc[i].size();
        for(int j=0; j<N; j++)
        {
            fout<<Ctc[i][j]<<" ";
        }
        fout<<'\n';
    }
}

int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
            DFS(i);
    while(!postordine.empty())
    {
        int X=postordine.top();
        if(viz[X]==1)
        {
            NrCtc++;
            DFST(X);
        }
        postordine.pop();
    }
    afisare();
    return 0;
}