Cod sursa(job #2927472)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 20 octombrie 2022 17:54:38
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
/**
 * La inceput facem o parcurgere in adancime pe graful initial si calculam o postordine
 * pentru acesta. Apoi luam nodurile in ordine inversa fata de cea din postordine si
 * facem cate o parcurgere in adancime  pe graful transpus pentru fiecare nod nevizitat.
 * Fiecare nod nevizitat impreuna cu nodurile nevizitate pe care le atinge in a doua 
 * parcurgere formeaza o componenta tare conexa.
 * Complexitate timp: O(N + M)
 * Complexitate memorie: O(N + M)
 */

#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5;

int n;
int m;
vector<int> graph[NMAX + 5];
vector<int> graphTranspose[NMAX + 5];
bool visited[NMAX + 5];
int idxPostOrder;
int postOrder[NMAX + 5];
vector<vector<int>> ctc;

void read() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graphTranspose[b].push_back(a);
    }
}

void dfs(int node) {
    visited[node] = true;
    for (int neighbour: graph[node])
        if (!visited[neighbour])
            dfs(neighbour);
    postOrder[idxPostOrder++] = node;
}

void dfsTranspose(int node) {
    visited[node] = false;
    ctc.back().push_back(node);
    for (int neighbour: graphTranspose[node])
        if (visited[neighbour])
            dfsTranspose(neighbour);
}

void computeCtc() {
    for (int i = 1; i <= n; i++)
        if (!visited[i])
            dfs(i);

    for (int i = n - 1; i >= 0; i--)
        if (visited[ postOrder[i] ]) {
            ctc.push_back(vector<int>());
            dfsTranspose(postOrder[i]);
        }
}

void print() {
    cout << ctc.size() << endl;
    for (vector<int> component: ctc) {
        for (int node: component)
            cout << node << " ";
        cout << endl;
    }
}

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

    read();
    computeCtc();
    print();

    return 0;
}