Cod sursa(job #2090021)

Utilizator Alex18maiAlex Enache Alex18mai Data 17 decembrie 2017 14:54:31
Problema Componente tare conexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, m;
vector<vector<int> > gr(100100);
vector<vector<int> > inv(100100);
vector<bool> used(100100);
vector<bool> USED(100100);
vector<vector<int> > ans;

queue<int> Q;
vector<int> verif;
map<int, bool> go;
vector<int> comp;

void BFS(int root) {

    Q.push(root);
    comp.clear();

    while (!Q.empty()) {

        int now = Q.front();
        Q.pop();
        USED[now] = true;
        comp.push_back(now);

        for (auto &x : inv[now]) {
            if (!USED[x] && go[x]) {
                Q.push(x);
            }
        }

    }

    ans.push_back(comp);

}

void bfs(int root) {

    Q.push(root);
    verif.clear();
    go.clear();

    while (!Q.empty()) {

        int now = Q.front();
        Q.pop();
        used[now] = true;
        go[now] = true;
        verif.push_back(now);

        for (auto &x : gr[now]) {
            if (!used[x]) {
                Q.push(x);
            }
        }

    }

    for (auto &x : verif) {
        if (!USED[x]) {
            BFS(x);
        }
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        gr[a].push_back(b);
        inv[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            continue;
        }

        bfs(i);
    }

    cout << ans.size() << '\n';

    for (auto &x : ans) {
        for (auto &y : x) {
            cout << y << " ";
        }
        cout << '\n';
    }


    return 0;
}