Cod sursa(job #1111016)

Utilizator eugen_ptrEugen Patru eugen_ptr Data 18 februarie 2014 16:24:14
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

#define Nmax 100005

using namespace std;

int viz[Nmax];
int apartenenta[Nmax];
int n,m;
int ctc;
vector <int> G[Nmax], Gt[Nmax];
stack <int> S;

void citire()
{
    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);
        Gt[y].push_back(x);
    }
}

void dfs(int nod)
{
    viz[nod] = 1;
    for(int i=0; i<G[nod].size(); i++)
        {
            int x = G[nod][i];
            if (!viz[x])
                dfs(x);
        }
    S.push(nod);
}

void primaParcurgere()
{
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);
}

void dfs2(int nod)
{
    apartenenta[nod] = ctc;
    for (int i=0; i<Gt[nod].size(); i++)
    {
        int x = Gt[nod][i];
        if (!apartenenta[x])
            dfs2(x);
    }
}

void aDouaParcurgere()
{
    ctc = 1;
    while(!S.empty())
    {
        int x = S.top();
        S.pop();
        if (!apartenenta[x])
        {
            dfs2(x);
            ctc++;
        }
    }
}

void afisare()
{
    ctc--;
    printf("%d\n",ctc);
    for (int i=1; i<=ctc; i++)
    {
        for (int j=1; j<=n; j++)
            if (apartenenta[j] == i)
                printf("%d ",j);
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    primaParcurgere();
    aDouaParcurgere();
    afisare();
    return 0;
}