Cod sursa(job #3195355)

Utilizator BogdanPPBogdan Protopopescu BogdanPP Data 20 ianuarie 2024 16:34:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
// Kosaraju

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define nmax 100001

int n, m, cnt = 0;
vector<vector<int>> graph(nmax), grapht(nmax);
vector<bool> visited(nmax, false);
vector<vector<int>> result(nmax);
stack<int> q;

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

   for (auto neighbour : graph[node])
   {
      if (!visited[neighbour])
      {
         visited[neighbour] = true;
         dfs(neighbour);
      }
   }
   q.push(node);
}

void dfst(int node, vector<int> &v)
{
   visited[node] = true;
   v.push_back(node);
   for (auto neighbour : grapht[node])
   {
      if (!visited[neighbour])
      {
         dfst(neighbour, v);
      }
   }
}

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

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

   visited.assign(nmax, false);
   while (!q.empty())
   {
      int node = q.top();
      q.pop();
      if (!visited[node])
      {
         dfst(node, result[++cnt]);
      }
   }
   fout << cnt << endl;
   for (int i = 1; i <= cnt; i++)
   {
      for (auto j : result[i])
      {
         fout << j << " ";
      }
      fout << endl;
   }
   return 0;
}