Cod sursa(job #1963436)

Utilizator adrianpopPop Adrian adrianpop Data 12 aprilie 2017 15:35:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
/*
    skel_graph - DFS
*/

#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

#define NMAX 100001
using namespace std;

int n, m;
vector<int> G[NMAX];
vector<int> Gp[NMAX];

vector<int> dfs_vect;
bitset<NMAX> used;

vector<vector<int>> ctc;
vector<int> partial;

void read_input() {
    int x, y;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        Gp[y].push_back(x);
    }
}

void dfsG(int node) {
    used[node] = 1;
    for (auto it = G[node].begin(); it != G[node].end(); ++it)
        if (!used[*it]) dfsG(*it);
    dfs_vect.push_back(node);
}

void dfsGp(int node) {
    used[node] = 1;
    for (auto it = Gp[node].begin(); it != Gp[node].end(); ++it)
        if (!used[*it]) dfsGp(*it);

    partial.push_back(node);
}

void solve() {
    // Efectuam sortarea topologica
    for (int i = 1; i <= n; ++i)
        if (!used[i])
            dfsG(i);

    // Resetam bitsetul
    used.reset();

    // Cautam CTC-urile
    for (int i = dfs_vect.size() - 1; i >= 0; --i) {
        if (!used[dfs_vect[i]]) {
            dfsGp(dfs_vect[i]);
            ctc.push_back(partial);
            partial.clear();
        }
    }
}

int main() {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    read_input();
    solve();

    printf("%d\n", ctc.size());
    for (int i = 0; i < ctc.size(); ++i) {
        for (int j = 0; j < ctc[i].size(); ++j) {
            printf("%d ", ctc[i][j]);
        }
        printf("\n");
    }

    fclose(stdout);
    fclose(stdin);
    return 0;
}