Cod sursa(job #2724699)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 17 martie 2021 18:12:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <stack>
#include <vector>
#include <bitset>

auto *in = fopen("sortaret.in", "r") ;
auto *out = fopen("sortaret.out", "w") ;

const int maxn = 1e5 ;

std::vector<int> G[1 + maxn] ;
std::vector<int> F[1 + maxn] ;
std::stack<int> sol ;
std::vector<int> curr ;
std::bitset<1 + maxn> seen1, seen2 ;

void dfs1(int node) {
    seen1[node] = 1;
    for (auto it : G[node]) {
        if (!seen1[it]) {
            dfs1(it) ;
        }
    }
    sol.push(node) ;
}

void dfs2(int node) {
    seen2[node] = 1;
    for (auto it : F[node]) {
        if (!seen2[it]) {
            dfs2(it) ;
        }
    }
    curr.push_back(node) ;
}

int main() {
    int n, m, x, y ;
    fscanf(in, "%d %d", &n, &m) ;
    for (int i = 1 ; i <= m ; ++ i) {
        fscanf(in, "%d %d", &x, &y) ;
        G[x].push_back(y) ;
        F[y].push_back(x) ;
    }
    for (int i = 1 ; i <= n ; ++ i) {
        if (!seen1[i]) {
            dfs1(i) ;
        }
    }
    std::vector<std::vector<int> > ret ;
    while (!sol.empty()) {
        if (!seen2[sol.top()]) {
            curr.clear() ;
            dfs2(sol.top());
            ret.push_back(curr) ;
        }
        sol.pop() ;
    }
    fprintf(out, "%d\n", ret.size()) ;
    for (auto it : ret) {
        for (int i = it.size() - 1 ; i >= 0 ; -- i) {
            fprintf(out, "%d ", it[i]) ;
        }
        fputc('\n', out) ;
    }
}