Cod sursa(job #2376444)

Utilizator akaprosAna Kapros akapros Data 8 martie 2019 15:41:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 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 > G[maxN];
static int t = 0;

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

int ans;
vector < int > C[maxN];
void dfs(int u)
{
    disc[u] = low[u] = ++ t;
    inSt[u] = true;
    st[++ top] = u;
    for (int v : G[u])
        if (!disc[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (inSt[v])
            low[u] = min(low[u], disc[v]);
    if (disc[u] == low[u])
    {
        comp[u] = ans;
        while (st[top] != u)
        {
            comp[st[top]] = ans;
            inSt[st[top]] = false;
            C[ans].push_back(st[top]);
            -- top;
        }
        C[ans].push_back(u);
        inSt[u] = false;
        -- top;
        ++ ans;
    }
}
int main()
{
    scanf("%d%d", &n, &m);

    while (m --)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for (int i = 1; i <= n; ++ i)
        if (!disc[i])
            dfs(i);

    printf("%d\n", ans);
    for (int i = 1; i <= n; ++ i)
        if (!inSt[comp[i]])
        {
            int j = comp[i];
            inSt[j] = true;
            sort(C[j].begin(), C[j].end());
            for (int u : C[j])
                printf("%d ", u);
            printf("\n");
        }
    return 0;
}