Cod sursa(job #1750624)

Utilizator antanaAntonia Boca antana Data 30 august 2016 16:42:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include<vector>
#define MAXN 100000
#define MAXM 200000

using namespace std;
vector<int>v[MAXN+1];

int ans, n, m, lista[MAXN+1], nxt[MAXM+1], val[MAXM+1], id[MAXN+1], st[MAXN+1], low[MAXN+1], index, p, k;
bool ok[MAXN+1];

inline int minim(int a, int b)
{
    return (a < b ? a : b);
}

inline void adauga(int x, int y)
{
    val[++p]=y;
    nxt[p]=lista[x];
    lista[x]=p;
}

void tarjan(int nod)
{
    int p, vecin;

    index++;
    id[nod]=low[nod]=index;
    st[++k]=nod;
    ok[nod]=1;

    p=lista[nod];
    while(p)
    {
        vecin=val[p];
        if(!id[vecin])
        {
            tarjan(vecin);
            low[nod]=minim(low[nod], low[vecin]);
        }
        else if(ok[vecin])
            low[nod]=minim(low[nod], low[vecin]);
        p=nxt[p];
    }

    if(low[nod]==id[nod])
    {
        ans++;
        while(st[k] != nod)
        {
            ok[st[k]]=0;
            v[ans].push_back(st[k]);
            --k;
        }
        v[ans].push_back(st[k]);
        ok[st[k]]=0;
        --k;
    }
}

void afisare()
{
    int i, j;

    printf("%d\n", ans);

    for(i=1;i<=ans;++i)
    {
        for(j=0;j<v[i].size();++j)
            printf("%d ", v[i][j]);
        printf("\n");
    }
}

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

    int i, x, y;

    scanf("%d%d", &n, &m);

    for(i=1;i<=m;++i)
        scanf("%d%d", &x, &y), adauga(x, y);

    for(i=1;i<=n;++i)
        if(!id[i])
            tarjan(i);

    afisare();

    return 0;
}