Cod sursa(job #2468742)

Utilizator Leonard1998Olariu Leonard Leonard1998 Data 5 octombrie 2019 21:39:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#include <vector>
#include <stack>

#define CTC_MAX (int)(1e5 + 5)

using namespace std;

int n, m, x, y;
vector<int> g[CTC_MAX], gt[CTC_MAX], ctc[CTC_MAX];
stack<int> postorder;
int viz[CTC_MAX], component[CTC_MAX];

void DFS (int x)
{
    viz[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
        if (!viz[g[x][i]])
            DFS(g[x][i]);

    postorder.push(x);
}

void DFST (int x, int ctcCount)
{
    component[x] = ctcCount;
    ctc[ctcCount].push_back (x);
    for (int i = 0; i < gt[x].size(); ++i)
        if (component[gt[x][i]] == 0)
            DFST (gt[x][i], ctcCount);
}

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

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

    for (int i = 1; i <= n; ++i)
        if (!viz[i]) DFS(i);

    int ctcCount = 0;
    while (!postorder.empty()) {
        if (component[postorder.top()] == 0) {
            ++ctcCount;
            DFST(postorder.top(), ctcCount);
        }

        postorder.pop();
    }

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

    return 0;
}