Cod sursa(job #1038330)

Utilizator kiralalaChitoraga Dumitru kiralala Data 21 noiembrie 2013 12:56:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#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],grapht[NMAX],compConexe[NMAX];
int used[NMAX];
int postord[NMAX],l,cont;
string outputprob;

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<grapht[k].size();++i)
                  if(used[grapht[k][i]])
                           DFS(grapht[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);
                  grapht[y].push_back(x);
         }

         for(int i=1;i<=n;++i)
                  if(!used[i])
                           DFSPostOrd(i);
         for(int i=l-1;i>=0;--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;
}