Cod sursa(job #2675401)

Utilizator maraboneaMara Bonea marabonea Data 21 noiembrie 2020 16:31:55
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
///infoarena.ro/problema/ctc
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define O 500000
using namespace std;

vector<int>  G[O],GT[O],R[O];
int viz[O];
int n,m,nr;
stack <int> s;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

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

void DFS1(int z)
{
    viz[z]=1;
    for(int i=0;i<G[z].size();i++)
    {
        int Vecin=G[z][i];
        if(viz[Vecin]==0)
            DFS1(Vecin);
    }
    s.push(z);
}
void DFS2(int z)
{
    viz[z]=2;
    R[nr].push_back(z);
    for(int i=0;i<GT[z].size();i++)
    {
        int Vecin=GT[z][i];
        if(viz[Vecin]==1)
            DFS2(Vecin);
    }
}
int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            DFS1(i);

    while(!s.empty())
    {
        int x=s.top();
        if(viz[x]==1)
        {
            nr++;
            DFS2(x);
        }
        s.pop();
    }
    fout<<nr<<endl;
    for(int i=1;i<=nr;i++)
    {
        for(int j=0;j<R[i].size();j++)
            fout<<R[i][j]<<" ";
        fout<<endl;
    }
    return 0;
}