Cod sursa(job #1098168)

Utilizator TeOOOVoina Teodora TeOOO Data 4 februarie 2014 16:30:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;

FILE *in,*out;

//Constante
const int sz = (int)1e5+1;

//Definitii
#define pb push_back

//Functii
void dfs(int node);
void backDFS(int node);

//Variabile
int nodes, edges;
bool visited[sz], inStack[sz];
vector <int> graph[sz], reversedGraph[sz];
stack <int> stacky;
vector < vector<int> > answer;
vector <int> temp;

//Main
int main()
{
   in = fopen("ctc.in","rt");
   out = fopen("ctc.out","wt");

   fscanf(in,"%d%d", &nodes, &edges);
   for(int i=1; i<=edges; ++i)
   {
       int from, to;
       fscanf(in,"%d%d", &from, &to);
       graph[from].pb(to);
       reversedGraph[to].pb(from);
   }

   for(int i=1; i<=nodes; ++i)
   {
       if(!inStack[i])
            dfs(i);
   }

   while(!stacky.empty())
   {
       int current = stacky.top();
       stacky.pop();

       if(inStack[current])
       {
           backDFS(current);
           answer.pb(temp);
           temp.clear();
       }
   }

   fprintf(out,"%d\n", answer.size());

   vector < vector<int> >::iterator it, end = answer.end();
   for(it = answer.begin(); it!=end; ++it)
   {
       vector<int>::iterator vit, vend = it->end();
       for(vit = it->begin(); vit!=vend; ++vit)
            fprintf(out,"%d ", *vit);
       fprintf(out,"\n");
   }

   fclose(in);
   fclose(out);
   return 0;
}

void dfs(int node)
{
    visited[node] = true;

    vector<int>::iterator it, end = graph[node].end();
    for(it = graph[node].begin(); it!=end; ++it)
        if(!visited[*it])
            dfs(*it);

    stacky.push(node);
    inStack[node] = true;
}

void backDFS(int node)
{
    inStack[node] = false;
    temp.pb(node);

    vector<int>::iterator it, end = reversedGraph[node].end();
    for(it = reversedGraph[node].begin(); it!=end; ++it)
        if(inStack[*it])
            backDFS(*it);

}