Cod sursa(job #1038332)

Utilizator kiralalaChitoraga Dumitru kiralala Data 21 noiembrie 2013 12:59:25
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<fstream>
#include<vector>
#include<string>
#define NMAX 100005

using namespace std;

FILE* f=freopen("ctc.in","r",stdin);
FILE* o=freopen("ctc.out","w",stdout);

int n,m;
vector<int> graph[NMAX];
int used[NMAX];
int postord[NMAX],l,cont;
vector<int> compConexe[NMAX];

void DFSPostOrd(int k)
{
         used[k]=1;
         for(int i=0;i<graph[k].size();++i)
                  if(!used[graph[k][i]])
                           DFSPostOrd(graph[k][i]);
         postord[l++]=k;
}

void DFS(int k)
{
         used[k]=0;
         compConexe[cont].push_back(k);
         for(int i=0;i<graph[k].size();++i)
                  if(used[graph[k][i]])
                  {
                           DFS(graph[k][i]);
                  }
}


int main()
{
         scanf("%d%d",&n,&m);

         for(int i=0;i<m;++i)
         {
                  int x,y;
                  scanf("%d%d",&x,&y);
                  graph[x].push_back(y);
         }

         for(int i=1;i<=n;++i)
                  if(!used[i])
                           DFSPostOrd(i);
         for(int i=0;i<l;++i)
                  if(used[postord[i]])
                  {
                           DFS(postord[i]);
                           cont+=1;
                  }

         printf("%d\n",cont);
         for(int i=0;i<cont;++i)
         {
                  for(int j=0;j<compConexe[i].size();++j)
                           printf("%d ",compConexe[i][j]);
                  printf("\n");
         }

         fclose(f);
         fclose(o);

         return 0;
}