Cod sursa(job #1250413)

Utilizator ZenusTudor Costin Razvan Zenus Data 28 octombrie 2014 08:49:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <cstring>

using namespace std;

#define NMAX 100007

vector < int > G[NMAX],T[NMAX],C[NMAX];
bool marked[NMAX];
stack < int > S;
int i,N,X,Y,ctc,M,current;

void df_1(int node)
{
    vector < int > :: iterator u;

    for (u=G[node].begin();u!=G[node].end();++u)
    {
        if (marked[*u]) continue;

        marked[*u]=true;
        df_1(*u);
    }

    S.push(node);
}

void df_2(int node)
{
    vector < int > :: iterator u;

    for (u=T[node].begin();u!=T[node].end();++u)
    {
        if (marked[*u]) continue;

        marked[*u]=true;
        df_2(*u);
    }

    C[ctc].push_back(node);
}

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

for (scanf("%d%d",&N,&M);M;--M)
{
    scanf("%d%d",&X,&Y);
    G[X].push_back(Y);
    T[Y].push_back(X);
}

for (i=1;i<=N;++i)
{
    if (marked[i]) continue;

    marked[i]=true;
    df_1(i);
}

memset(marked,false,sizeof(marked));
while (!S.empty())
{
    current=S.top();
    S.pop();

    if (marked[current]) continue;

    ++ctc;
    marked[current]=true;

    df_2(current);
}

for (printf("%d\n",ctc),i=1;i<=ctc;++i,printf("\n"))
for (vector < int > :: iterator u=C[i].begin();u!=C[i].end();++u)
printf("%d ",*u);

return 0;
}