Cod sursa(job #3337045)

Utilizator andrei0925Andrei Perdevara andrei0925 Data 26 ianuarie 2026 21:14:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define NMAX 100005
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N, M, x, y, f[NMAX], cntscc;

vector <int> G[NMAX];
vector <int> Gt[NMAX];
vector <int> scc[NMAX];
vector <int> sortare;

queue <int> q;

void dfs1(int x)
{
  f[x] = 1;
  for(auto e : G[x])
    if(f[e] == 0)
      dfs1(e);
  sortare.push_back(x);
}

void dfs(int x)
{
  f[x] = 1;
  scc[cntscc].push_back(x);
  for(auto e : Gt[x])
    if(f[e] == 0)
      dfs(e);
}

int main()
{
  cin >> N >> M;
  for(int i = 1; i <= M; i++)
  {
    cin >> x >> y;
    G[x].push_back(y);
    Gt[y].push_back(x);
  }
  //facem sortarea
  for(int i = 1; i <= N; i++)
    if(f[i] == 0)
      dfs1(i);

  reverse(sortare.begin(), sortare.end());

  for(int i = 1; i <= N; i++)
      f[i] = 0;

  //costruim scc
  for(auto i : sortare)
  {
    if(f[i] == 0)
    {
      cntscc++;
      dfs(i);
    }
  }
  cout << cntscc <<'\n';
  for(int i = 1; i <= cntscc; i++)
  {
    sort(scc[i].begin(), scc[i].end());
    for(auto e : scc[i])
      cout << e << ' ';
    cout<<'\n';
  }
  return 0;
}