Cod sursa(job #2118729)

Utilizator remus88Neatu Remus Mihai remus88 Data 30 ianuarie 2018 21:51:13
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <bitset>
#define Nmax 100009

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

int n,m,x,y,tsort[Nmax],nr,nrc;
vector <int> G[Nmax],T[Nmax],ctc[Nmax];
bitset <Nmax> viz;

void DFS(int node) {

    viz[node]=1;
    for (auto x : G[node])
        if (!viz[x]) DFS(x);

    ++nr;
    tsort[nr]=node;
}

void DFS_T(int node) {

    viz[node]=0;
    ctc[nrc].push_back(node);

    for (auto x : T[node])
        if (viz[x]) DFS_T(x);
}

void ReadInput() {

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

void Solve() {

    for (int i=1; i<=n; ++i)
        if (!viz[i]) DFS(i);

    for (int i=1; i<=n; ++i)
        if (viz[i]) {
            ++nrc;
            DFS_T(i);
        }
}

void Write() {

    g<<nrc<<'\n';
    for (int i=1; i<=n; ++i) {
        for (auto x : ctc[i]) g<<x<<' ';
        g<<'\n';
    }
}

int main() {

    ReadInput();
    Solve();
    Write();
    f.close(); g.close();
    return 0;
}