Cod sursa(job #1923646)

Utilizator M.AndreiMuntea Andrei Marius M.Andrei Data 11 martie 2017 20:30:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 100005

ifstream f{ "ctc.in" };
ofstream q{ "ctc.out" };

vector<int> graph[NMAX];
vector<int> stack;
vector< vector<int> >sol;
int  visited[NMAX], lowLink[NMAX];
bool onStack[NMAX];
int index = 1;
int n, m;

void read()
{
   int x, y;
   f >> n >> m;
   for(int i = 0; i < m; ++i)
   {
      f >> x >> y;
      graph[x].push_back(y);
   }
}

void printComponent()
{
   q << sol.size() << "\n";
   for(auto& comp : sol)
   {
      for (auto& c : comp) q << c << " ";
      q << "\n";
   }
}


void tarjan(int node)
{
   visited[node] = index;
   lowLink[node] = index;
   onStack[node] = true;
   stack.push_back(node);
   index++;
   for(auto vec : graph[node])
   {
      if (visited[vec] == 0)
      {
         tarjan(vec);
         lowLink[node] = min(lowLink[node], lowLink[vec]);
      }
      else if (onStack[vec])
      {
         lowLink[node] = min(lowLink[node], lowLink[vec]);
      }
   }
   if (lowLink[node] == visited[node])
   {
      vector<int> currentComponent;
      int c;
      do
      {
         c = stack.back();
         currentComponent.push_back(c);
         stack.pop_back();
         onStack[c] = false;
      } while (c != node);
      sol.push_back(currentComponent);
   }
}

int main()
{
   read();
   for(int i = 1; i<=n; ++i)
   {
      if (visited[i] == 0) tarjan(i);
   }

   printComponent();

   f.close();
   q.close();
   return 0;
}