Cod sursa(job #1181592)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 3 mai 2014 11:24:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>
#define Nmax 100005

using namespace std;

int N,st[Nmax],nrsol;
bool viz[Nmax];
vector <int> L[Nmax],T[Nmax],sol[Nmax];

inline void Dfs(int nod)
{
    viz[nod]=true;
    vector <int>::iterator it;
    for(it=L[nod].begin();it!=L[nod].end();++it)
        if(!viz[*it])
            Dfs(*it);
    st[++st[0]]=nod;
}

inline void Dfs2(int nod)
{
    viz[nod]=true;
    vector <int>::iterator it;
    for(it=T[nod].begin();it!=T[nod].end();++it)
        if(!viz[*it])
            Dfs2(*it);
    sol[nrsol].push_back(nod);
}

int main()
{
    int M,x,y,i,nod;
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    scanf("%d%d", &N,&M);
    while(M--)
    {
        scanf("%d%d", &x,&y);
        L[x].push_back(y);
        T[y].push_back(x);
    }
    for(i=1;i<=N;++i)
        if(!viz[i])
            Dfs(i);
    for(i=1;i<=N;++i)
        viz[i]=false;
    while(st[0])
    {
        nod=st[st[0]--];
        if(!viz[nod])
        {
            ++nrsol;
            Dfs2(nod);
        }
    }
    printf("%d\n", nrsol);
    for(i=1;i<=nrsol;++i)
    {
        vector <int>::iterator it;
        for(it=sol[i].begin();it!=sol[i].end();++it)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}