Cod sursa(job #1038326)

Utilizator kiralalaChitoraga Dumitru kiralala Data 21 noiembrie 2013 12:48:59
Problema Componente tare conexe Scor 46
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],grapht[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;
         outputprob+=(k+'0');
         outputprob+=' ';
         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]])
                  {
                           cont+=1;
                           DFS(postord[i]);
                           outputprob+="\n";
                  }

         printf("%d\n",cont);
         for(int i=0;i<outputprob.length();++i)
                  printf("%c",outputprob[i]);

         fclose(f);
         fclose(o);

         return 0;
}