Cod sursa(job #1913897)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 8 martie 2017 14:36:42
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100010;
const int MMAX = 200010;

int N, M;

vector<int> G[NMAX];
vector<int> T[NMAX];
vector<int> ord;
vector<int> ctc[NMAX];

int viz1[NMAX];
void DFS1 (int nod) {
    viz1[nod] = 1;
    ord.push_back(nod);
    for (auto &it : G[nod]) {
        if ( !viz1[it]) {
            DFS1(it);
        }
    }
}

int viz2[NMAX];
void DFS2 (int nod, int indCtc) {
    viz2[nod] = 1;
    ctc[indCtc].push_back (nod);
    for (auto &it : T[nod]) {
        if ( !viz2[it]) {
            DFS2(it, indCtc);
        }
     }
}

int main () {
    fin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back (y);
        T[y].push_back (x);
    }

    for (int i = 1; i <= N; i++) {
        if ( !viz1[i]) {
            DFS1 (i);
        }
    }

    int nrCtc = 0;
    for (auto &it : ord) {
        if ( !viz2[it]) {
            nrCtc ++;
            DFS2 (it, nrCtc);
        }
    }
    fout << nrCtc << '\n';
    for (int i = 1; i <= nrCtc; i++) {
        for (auto &it : ctc[i]) {
            fout << it << " ";
        }
        fout << '\n';
    }

    return 0;
}