Cod sursa(job #2927475)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 20 octombrie 2022 17:58:43
Problema Componente tare conexe Scor 100
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];
int nrCtc;
vector<int> ctc[NMAX + 5];

void read() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &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[nrCtc].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] ]) {
            dfsTranspose(postOrder[i]);
            nrCtc++;
        }
}

void print() {
    printf("%d\n", nrCtc);
    for (int i = 0; i < nrCtc; i++) {
        for (int node: ctc[i])
            printf("%d ", node);
        printf("\n");
    }
}

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

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

    return 0;
}