Cod sursa(job #1216709)

Utilizator ZenusTudor Costin Razvan Zenus Data 5 august 2014 15:05:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

#define NMAX 200007

vector < int > G[NMAX],T[NMAX],C[NMAX];
bool sel[NMAX];
queue < int > Q;
int N,M,i,e,current,X,Y;
stack < int > S;

void df(int node)
{
    vector < int > :: iterator i;

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

        sel[*i]=true;
        df(*i);
    }

    S.push(node);
}

void specialdf(int start)
{
    vector < int > :: iterator i;
    int node;

    Q.push(start);
    sel[start]=true;

    while (!Q.empty())
    {
        node=Q.front();
        C[e].push_back(node);

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

            sel[*i]=true;
            Q.push(*i);
        }
        Q.pop();
    }
}

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

scanf("%d%d",&N,&M);

while (M--)
{
    scanf("%d%d",&X,&Y);

    G[X].push_back(Y);
    T[Y].push_back(X);
}

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

    df(i);
}

memset(sel,false,sizeof(sel));

while (!S.empty())
{
    current=S.top();
    S.pop();

    if (sel[current])
    continue;

    ++e;
    specialdf(current);
}

for (i=1,printf("%d\n",e);i<=e;++i,printf("\n"))
{
    sort(C[i].begin(),C[i].end());

    for (vector < int > :: iterator j=C[i].begin();j!=C[i].end();++j)
    printf("%d ",*j);
}

return 0;
}