Cod sursa(job #2090024)

Utilizator Alex18maiAlex Enache Alex18mai Data 17 decembrie 2017 15:07:30
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 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);
    USED[root] = true;
    comp.clear();

    while (!Q.empty()) {

        int now = Q.front();
        Q.pop();
        comp.push_back(now);
        //cout<<now<<'\n';

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

    }

    ans.push_back(comp);

}

void bfs(int root) {

    Q.push(root);
    used[root] = true;
    verif.clear();
    go.clear();

    while (!Q.empty()) {

        int now = Q.front();
        Q.pop();
        go[now] = true;
        verif.push_back(now);
        //cout<<now<<'\n';

        for (auto &x : gr[now]) {
            if (!used[x]) {
                used[x] = true;
                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;
}