Cod sursa(job #3222000)

Utilizator IoanMasterUngureanu Ioan IoanMaster Data 8 aprilie 2024 20:31:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <stack>

using namespace std;
vector<bool> visited;
vector<vector<int>> Result;

stack<int> S;

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

int n, m, nrc;
vector<vector<int>> Graph, Graph_reverse;

void read()
{
  int x, y, i;
  fin >> n >> m;

  Graph.resize(n + 5), Graph_reverse.resize(n + 5), visited.resize(n + 5), Result.resize(n + 5);

  for (i = 1; i <= m; i++)
  {
    fin >> x >> y;
    Graph[x].push_back(y);
    Graph_reverse[y].push_back(x);
  }
}

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

  for (vector<int>::iterator it = Graph[node].begin(); it != Graph[node].end(); it++)
  {
    if (!visited[*it])
      DFS1(*it);
  }

  S.push(node);
}

void DFS2(int node)
{
  Result[nrc].push_back(node);
  visited[node] = true;

  for (vector<int>::iterator it = Graph_reverse[node].begin(); it != Graph_reverse[node].end(); it++)
  {
    if (!visited[*it])
      DFS2(*it);
  }

  S.push(node);
}

int main()
{
  read();

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

  for (int i = 1; i <= n; i++)
    visited[i] = false;

  while (!S.empty())
  {
    int varf = S.top();
    S.pop();

    if (!visited[varf])
    {
      nrc++;
      DFS2(varf);
    }
  }

  fout << nrc << '\n';

  for (int i = 1; i <= nrc; i++)
  {
    for (vector<int>::iterator it = Result[i].begin(); it != Result[i].end(); it++)
      fout << *it << ' ';

    fout << '\n';
  }

  fin.close(), fout.close();

  return 0;
}