Cod sursa(job #2724710)

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

#ifndef InputReader_H
#define InputReader_H

#include <cstdio>

template <typename T>
class InputReader {
private:
    FILE *input_file ;
    static const int SIZE = (1 << 17) ;
    int point ;
    char buffer[SIZE] ;
    __attribute__ ( (always_inline)) void advance() {
        ++ point ;
        if (point == SIZE) {
            point = 0 ;
            fread (buffer, SIZE, 1, input_file) ;
        }
    }
public:
    InputReader() {}
    InputReader (const char *file_name) {
        input_file = fopen (file_name, "r") ;
        point = 0 ;
        fread (buffer, SIZE, 1, input_file) ;
    }
    __attribute__ ( (always_inline)) InputReader &operator >> (T &n) {
        for (; !isdigit (buffer[point]) ; advance()) ;
        n = 0 ;
        for (; isdigit (buffer[point]) ; advance()) {
            n = n * 10 + buffer[point] - '0' ;
        }
        return *this ;
    }
} ;

#endif //UNTITLED1_LIBRARY_H
InputReader<int> in ("ctc.in") ;

//
// Created by Euraba on 03.03.2021.
//

#ifndef OUTPARSING_H
#define OUTPARSING_H


#include <ios>
#include <fstream>

class OutputParsing {
public:
    OutputParsing() {} ;

    OutputParsing(const char * file_name) {
        output_file.open(file_name, std::ios::out | std::ios::binary) ;
        output_file.sync_with_stdio(false) ;
        index = 0 ;
    }

    inline OutputParsing & operator << (int target) {
        aux = 0 ;
        n = target ;
        target < 0 ? sign = -1 : sign = 1 ;
        if (!n) {
            nr[aux ++] = '0' ;
        }
        for ( ; n ; n /= 10) {
            nr[aux ++] = sign * (n % 10) + '0' ;
        }
        if (sign == -1) {
            buffer[index] = '-' ;
            inc() ;
        }
        for ( ; aux ; inc())
            buffer[index] = nr[-- aux] ;
        return *this ;
    }

    inline OutputParsing & operator << (const char * target) {
        aux = 0 ;
        while (target[aux]) {
            buffer[index] = target[aux ++] ;
            inc() ;
        }
        return *this ;
    }
    ~OutputParsing() {
        output_file.write(buffer, index) ;
        output_file.close() ;
    }

private:
    std::fstream output_file;
    static const int SIZE = 0x200000;
    int index = 0, aux, n, sign;
    char buffer[SIZE], nr[24];

    inline void inc() {
        if (++index == SIZE) {
            index = 0 ;
            output_file.write(buffer, SIZE);
        }
    }
} ;


#endif //OUTPARSING_H
OutputParsing out ("ctc.out") ;

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 ;
    in >> n >> m ;
    for (int i = 1 ; i <= m ; ++ i) {
        in >> 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() ;
    }
    out << ret.size() ;
    for (auto it : ret) {
        for (int i = it.size() - 1 ; i >= 0 ; -- i) {
           out << it[i] ;
        }
        out << "\n" ;
    }
}