Cod sursa(job #1519205)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 6 noiembrie 2015 23:34:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;
const int MAX_M = 200000 + 1;
const int NIL = -1;

struct Graph
{
    struct Edge
    {
        int v;
        int urm;
    };

    Edge G[MAX_M];
    int head[MAX_N];
    int contor;

    Graph() : contor(0) {

        for (int i = 1; i < MAX_N; ++i)
            head[i] = NIL;
    }

    void addEdge(int x, int y)
    {
        G[contor] = {y, head[x]};
        head[x] = contor++;
    }
};

Graph G, GT;
bool visited[MAX_N];
int sorted[MAX_N];
vector<vector<int>> ANS;

int N, M;
int dim = 0;

int getInt()
{
    int x;
    scanf("%d", &x);

    return x;
}

void dfs(int node)
{
    visited[node] = true;

    for (int p = G.head[node]; p != NIL; p = G.G[p].urm)
    {
        int v = G.G[p].v;

        if (!visited[v])
            dfs(v);
    }

    sorted[ ++dim ] = node;
}

void dfsT(int node, vector<int> &ctc)
{
    ctc.emplace_back(node);

    visited[node] = false;

    for (int p = GT.head[node]; p != NIL; p = GT.G[p].urm)
    {
        int v = GT.G[p].v;

        if (visited[v])
            dfsT(v, ctc);
    }
}

void kosaraju()
{
    for (int i = N; i >= 1; i--)
    {
        int node = sorted[i];

        if (visited[node])
        {
            vector<int> ctc;
            dfsT(node, ctc);

            ANS.emplace_back(ctc);
        }
    }
}

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

    N = getInt(); M = getInt();

    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        x = getInt(); y = getInt();

        G.addEdge(x, y);
        GT.addEdge(y, x);
    }

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

    kosaraju();

    printf("%d\n", (int)ANS.size());

    for (size_t i = 0; i < ANS.size(); ++i)
    {
        for (int x : ANS[i])
            printf("%d ", x);

        printf("\n");
    }

    return 0;
}