Cod sursa(job #469962)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 9 iulie 2010 23:16:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define file_in "ctc.in"
#define file_out "ctc.out"

#define nmax 123232

int n,m;
vector<int> G[nmax];
vector<int> Gt[nmax];
vector<int> sol[nmax];
int nr,ord[nmax];
int viz[nmax];

void citire()
{
    int a,b;
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d %d", &n, &m);
    while(m--)
    {
        scanf("%d %d", &a, &b);

        G[a].push_back(b);
        Gt[b].push_back(a);
    }

}

void dfs(int nod)
{
    if (viz[nod])
    return ;

    viz[nod]=1;

    int i;

    for (i=0;i<G[nod].size();++i)
         if (!viz[G[nod][i]])
         {
             dfs(G[nod][i]);
         }
          ord[++nr]=nod;
}

void dfst(int nod)
{
    if (viz[nod])
    return ;

    viz[nod]=1;
    sol[nr].push_back(nod);
    int i;

    for (i=0;i<Gt[nod].size();++i)
         if (!viz[Gt[nod][i]])
         {
             dfst(Gt[nod][i]);
         }
}

void solve()
{
    int i,j;
    nr=0;
    memset(viz,0,sizeof(viz));
    for (i=1;i<=n;++i)
      if (!viz[i])
       dfs(i);

       memset(viz,0,sizeof(viz));
       nr=0;
       for (i=n;i>=1;--i)
      if (!viz[ord[i]])
      {
          nr++;
          dfst(ord[i]);
      }

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

}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}