Cod sursa(job #2368166)

Utilizator BlkAlexAlex Negru BlkAlex Data 5 martie 2019 14:23:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
#define MAX 100100

using namespace std;

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

bool viz[MAX];
vector <int> G[MAX];
vector <int> Gi[MAX];
vector <int> rez[MAX];
stack <int> S;
int n, m, nrc;

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

void dfs (int node){
    viz[node] = true;
    for (int i = 0 ; i < G[node].size(); ++i){
        int newnode = G[node][i];
        if (!viz[newnode]){
            dfs(newnode);
        }
    }
    S.push(node);
}

void dfsi (int node){
    viz[node] = true;
    rez[nrc].push_back(node);
    for (int i = 0 ; i < Gi[node].size(); ++i){
        int newnode = Gi[node][i];
        if (!viz[newnode]){
            dfsi(newnode);
        }
    }
}

void vizclear(){
    for (int i = 1; i <= n; i++){
        viz[i] = false;
    }
}

void afish(){
    g << nrc << '\n';
    for (int k = 1; k <= nrc; ++k){
        for (int i = 0; i < rez[k].size(); i++){
            g << rez[k][i] << ' ';
        }
        g << '\n';
    }
}

void domorestuff(){
    vizclear();
    for (int i = 1; i <= n; i++){
        if (viz[i] == false){
            dfs(i);
        }
    }
    vizclear();
    while (!S.empty()){
        int stop;
        stop = S.top();
        S.pop();
        if (!viz[stop]){
            nrc++;
            dfsi(stop);
        }
    }
    afish();
}

int main()
{
    dostuff();
    domorestuff();
    return 0;
}