Cod sursa(job #2681183)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 5 decembrie 2020 09:38:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;

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

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

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

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

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

void parcurgere(){
    for(int i=1; i<=n; i++)
        if(viz[i] == 0)
            DFS(i);
}

void solve(){
    while(!s.empty()){
        int vf = s.top();
        s.pop();
        if(viz[vf] < 0)
            continue;
        nrc++;
        DFSt(vf, nrc);
    }
}

void afis(){
    g<<nrc<<'\n';
    for(int i=1; i<=nrc; i++){
        for(auto &v:comp[i])
            g<<v<<' ';
        g<<'\n';
    }
}
int main()
{
    citire();
    parcurgere();
    solve();
    afis();
    return 0;
}