Cod sursa(job #2416282)

Utilizator akaprosAna Kapros akapros Data 27 aprilie 2019 12:06:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
#define maxN 100002

using namespace std;


FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);

int n, m;
vector < int > V[maxN];

int T, disc[maxN], low[maxN], nrC;
bool inSt[maxN];
int top, st[maxN];

vector < int > C[maxN];

void Ctc(int u)
{
    ++ nrC;
    while (top > 0)
    {
        int crt = st[top];
        -- top;
        C[nrC].push_back(crt);
        inSt[crt] = false;
        if (crt == u) break;
    }
}
void dfs(int u, int par)
{
    disc[u] = low[u] = ++ T;
    st[++ top] = u;
    inSt[u] = true;
    for (int v : V[u])
        if (!disc[v])
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if (inSt[v])
        {
            low[u] = min(low[u], disc[v]);
        }
    if (low[u] == disc[u])
        Ctc(u);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++ i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        -- u;
        -- v;
        V[u].push_back(v);
    }
    for (int i = 0; i < n; ++ i)
        if (!disc[i])
            dfs(i, -1);
    printf("%d\n", nrC);
    for (int i = 1; i <= nrC; ++ i, printf("\n"))
        for (auto it : C[i])
            printf("%d ", it + 1);
    return 0;
}