Cod sursa(job #1192661)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 29 mai 2014 14:58:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <vector>

using namespace std;
int i,j,x,y,n,m,sol,V[100009],nr=0;
bool sel[100009];
vector<int> G[100009],Gt[100009],S[100009];

void dfs(int x)
{
   int i;

   sel[x]=true;

   for(i=0;i<G[x].size();++i)
   if(!sel[G[x][i]])
   dfs(G[x][i]);

   V[++nr]=x;




}

void dfst(int x)
{
   int i;

   sel[x]=true;

   for(i=0;i<Gt[x].size();++i)
   if(!sel[Gt[x][i]])
   dfst(Gt[x][i]);

   S[sol].push_back(x);

}

int main()
{
    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);
       G[x].push_back(y);
       Gt[y].push_back(x);

    }

    nr=0;

    for(i=1;i<=n;++i)
    sel[i]=false;

    for(i=1;i<=n;++i)
    if(!sel[i])
    dfs(i);

    for(i=1;i<=n;++i)
    sel[i]=false;

    for(i=n;i>=1;--i)
    if(!sel[V[i]])
    {
       ++sol;
       dfst(V[i]);

    }

    printf("%d\n",sol);
    for(i=1;i<=sol;++i)
    {
       for(j=0;j<S[i].size();++j)
       printf("%d ",S[i][j]);
       printf("\n");

    }







    return 0;
}