Cod sursa(job #2291464)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 28 noiembrie 2018 01:14:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100005;
const int MMAX = 200005;

int N, M;

vector<int> G[NMAX];

int low[NMAX];
int  id[NMAX];
bool onStack[NMAX];
bool visited[NMAX];

stack<int> node_stack;

int id_count = 0;

vector<vector<int>> sol;


void dfs(int i) {
   onStack[i] = true;
   visited[i] = true;
   id[i] = low[i] = id_count++;
   node_stack.push(i);

   for (auto node : G[i]) {
      if (!visited[node]) {
         dfs(node);
      }
      if (onStack[node]) {
         low[i] = min(low[i], low[node]);
      }
   }

   if (id[i] == low[i]) {
      vector<int> ctc;
      while (!node_stack.empty()) {
         int top = node_stack.top();
         low[top] = id[i];

         ctc.push_back(top);
         node_stack.pop();
         onStack[top] = false;
         if (top == i) {
            break;
         }

      }
      sol.push_back(ctc);
   }
}

void tarjan() {
   for (int i = 1; i <= N; ++i) {
      if (!visited[i]) {
         dfs(i);
      }
   }
}

int main() {
   freopen("ctc.in", "r", stdin);
   freopen("ctc.out", "w", stdout);

   scanf("%d %d", &N, &M);

   for (int i = 1; i <= M; ++i) {
      int x, y;
      scanf("%d %d", &x, &y);
      G[x].push_back(y);
   }

   tarjan();

   printf("%d\n", int(sol.size()));

   for (auto ctc : sol) {
      for (auto node : ctc) {
         printf("%d ", node);
      }
      printf("\n");
   }


   fclose(stdin);
   fclose(stdout);
   return 0;
}