Cod sursa(job #1165305)

Utilizator darrenRares Buhai darren Data 2 aprilie 2014 16:55:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
int where[100002], whmin[100002];
int comps;
vector<int> comp[100002];
int ST[100002];
bool inST[100002];

void Tarjan(int x)
{
    where[x] = ++where[0];
    whmin[x] = where[x];
    ST[++ST[0]] = x;
    inST[x] = true;

    for (auto it = V[x].begin(); it != V[x].end(); ++it)
    {
        if (!where[*it])
            Tarjan(*it);
        if (inST[*it])
            whmin[x] = min(whmin[x], whmin[*it]);
    }

    if (where[x] == whmin[x])
    {
        ++comps;
        while (true)
        {
            comp[comps].push_back(ST[ST[0]]);
            --ST[0];
            inST[ST[ST[0] + 1]] = false;
            if (ST[ST[0] + 1] == x) break;
        }
    }
}

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

    scanf("%d %d", &N, &M);
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        scanf("%d %d", &nod1, &nod2);
        V[nod1].push_back(nod2);
    }

    for (int i = 1; i <= N; ++i)
        if (!where[i])
            Tarjan(i);

    printf("%d\n", comps);
    for (int i = 1; i <= comps; ++i)
    {
        for (auto it = comp[i].begin(); it != comp[i].end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
}