Cod sursa(job #2681182)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 5 decembrie 2020 09:37:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#define NMAX 100005
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

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

int n, m, nrc, viz[NMAX];
vector<int> graph[NMAX], gt[NMAX];
stack<int> S;
vector<int> cc[NMAX];

void read()
{
    int x, y;

    f>>n>>m;
    for(int i = 0; i < m; ++i)
    {
        f>>x>>y;
        graph[x].push_back(y);
        gt[y].push_back(x);
    }
}

void DFS(int vf)
{
    viz[vf] = -1;
    for(auto &v:graph[vf])
        if(viz[v] == 0)
            DFS(v);
    S.push(vf);
}

void DFSt(int vf, int nrc)
{
    viz[vf] = 1;
    for(auto &v:gt[vf])
        if(viz[v] < 0)
            DFSt(v, nrc);
    cc[nrc].push_back(vf);
}

void write()
{
    g<<nrc<<'\n';
    for(int i = 1; i <= nrc; ++i)
    {
        for(auto &v:cc[i])
            g<<v<<' ';
        g<<'\n';
    }
}



int main()
{
    read();
    for(int i = 1; i <= n; ++i)
        if(viz[i] == 0)
            DFS(i);
    while(!S.empty())
    {
        int vf = S.top();
        S.pop();
        if(viz[vf] > 0)
            continue;
        nrc++;
        DFSt(vf, nrc);
    }
    write();
    return 0;
}