Cod sursa(job #932980)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 29 martie 2013 14:38:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<stack>
#include<vector>
#define NMax 100005
using namespace std;

int idx[NMax],lowlink[NMax];
int in_st[NMax],crt,nr_ctc;
vector<int> vc[NMax],ctc[NMax];
stack<int> S;

void df (int nod)
{
    crt++;
    idx[nod]=crt;
    lowlink[nod]=crt;
    S.push(nod), in_st[nod]=1;
    int i,lg=vc[nod].size();
    for (i=0; i<lg; i++)
        if (!idx[vc[nod][i]])
        {
            df(vc[nod][i]);
            lowlink[nod]=min(lowlink[nod],lowlink[vc[nod][i]]);
        }
        else if (in_st[vc[nod][i]])
            lowlink[nod]=min(lowlink[nod],idx[vc[nod][i]]);
    if (idx[nod]==lowlink[nod])
    {
        nr_ctc++;
        int aux;
        do
        {
            aux=S.top(), S.pop();
            in_st[aux]=0;
            ctc[nr_ctc].push_back(aux);
        } while (aux!=nod);
    }
}

int main ()
{
    int n,m,i,lg,x,y,j;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        vc[x].push_back(y);
    }
    for (i=1; i<=n; i++)
        if (!idx[i])
            df(i);
    printf("%d\n",nr_ctc);
    for (i=1; i<=nr_ctc; i++, printf("\n"))
    {
        lg=ctc[i].size();
        for (j=0; j<lg; j++)
            printf("%d ",ctc[i][j]);
    }
    return 0;
}