Cod sursa(job #1538383)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 noiembrie 2015 22:17:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;

vector<int> G[MAX_N];
vector<int> GT[MAX_N];
vector<int> SCC[MAX_N];

int visited[MAX_N];
int topsort[MAX_N], P;

int N, M;
int nrSCC;

void dfs(int nod)
{
    visited[nod] = 1;

    for (int v : G[nod])
        if (!visited[v])
            dfs(v);

    topsort[ ++P ] = nod;
}

void dfsT(int nod)
{
    SCC[nrSCC].emplace_back(nod);
    visited[nod] = 0;

    for (int v : GT[nod])
        if (visited[v])
            dfsT(v);
}

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

    for (int i = P; i >= 1; i--)
        if (visited[ topsort[i] ])
        {
            nrSCC++;
            dfsT(topsort[i]);
        }
}

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

    scanf("%d %d", &N, &M);

    while (M--)
    {
        int x, y;
        scanf("%d%d", &x, &y);

        G[x].emplace_back(y);
        GT[y].emplace_back(x);
    }

    plus_minus();

    printf("%d\n", nrSCC);

    for (int i = 1; i <= nrSCC; ++i)
    {
        for (int x : SCC[i])
            printf("%d ", x);

        puts("");
    }

    return 0;
}