Cod sursa(job #2481088)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 26 octombrie 2019 13:42:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int nmax = 100000;

vector <int> g1[nmax + 5], g2[nmax + 5], s[nmax + 5];
int n, m, use[nmax + 5], v[nmax + 5], k, x, aux = 1;

void Read(){
    fin >> n >> m;
    while (m--){
        int x, y;
        fin >> x >> y;
        g1[x].push_back(y);
        g2[y].push_back(x);
    }
}

void Sort(int nod){
    use[nod] = 1;
    for (auto i : g1[nod])
        if (!use[i])
            Sort(i);
    v[++k] = nod;
}

void DFS(int nod, int x){
    use[nod] = x;
    s[x].push_back(nod);
    for (auto i : g2[nod])
        if (!use[i])
            DFS(i, x);
}

void Solve(){
    for (int i = 1; i <= n; i++)
        if (!use[i])
            Sort(i);
    memset(use, 0, sizeof use);
    for (int i = n; i >= 1; i--)
        if (!use[v[i]]){
            DFS(v[i], aux);
            aux++;
        }
}

void Print(){
    fout << aux - 1 << '\n';
    for (int i = 1; i < aux; i++){
        for (auto j : s[i])
            fout << j << ' ';
        fout << '\n';
    }
}

int main(){
    Read();
    Solve();
    Print();
    return 0;
}