Cod sursa(job #1659962)

Utilizator papinubPapa Victor papinub Data 22 martie 2016 18:40:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
# include <cstdio>
# include <vector>
# include <algorithm>
# include <stack>
using namespace std;

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

const int N_MAX = 100001;

vector <int> G[N_MAX];
vector <int> sol[N_MAX];
stack <int> S;

int lowlink[N_MAX];
bool in_stiva[N_MAX];
int n, m, index, total;
int idx[N_MAX];

void read()
{
    scanf("%d %d", &n, &m);

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

        scanf("%d %d", &x, &y);

        G[x].push_back(y);
    }
}

void dfs(int nod)
{
    index ++;
    idx[nod] = index;

    lowlink[nod] = index;
    S.push(nod);
    in_stiva[nod] = true;

    for (int i : G[nod])
    {
        if (!lowlink[i])
        {
            dfs(i);
            lowlink[nod] = min(lowlink[nod], lowlink[i]);
        }
        else
            if (in_stiva[i])
                lowlink[nod] = min(lowlink[nod], lowlink[i]);
    }

    if (lowlink[nod] == idx[nod])
    {
        int it;

        it = S.top();
        total ++;

        while (it != nod)
        {
            /// printf("%d ", it);
            sol[total].push_back(it);
            in_stiva[it] = false;
            S.pop();
            it = S.top();
        }

        /// printf("%d ", it);

        sol[total].push_back(it);
        S.pop();
        in_stiva[it] = false;
    }
}

void write()
{
    printf("%d\n", total);

    for (int i=1; i<=total; i++)
    {
        for (int j : sol[i])
        {
            printf("%d ", j);
        }
        printf("\n");
    }
}

int main()
{
    read();
    for (int i=1; i<=n; i++)
    {
        if (!lowlink[i])
            dfs(i);
    }
    write();
    return 0;
}