Cod sursa(job #3303676)

Utilizator cutuslabutuNegrila Florin cutuslabutu Data 17 iulie 2025 10:23:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
const int Max = 5e5 + 10;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, q, M, t;

vector<int> G[Max];
vector<int> Gt[Max];
vector<int> S;
int vis[Max];
int comp[Max];

void sort_top(int node)
{
    vis[node] = 1;
    for(auto nxt : G[node])
    {
      if(!vis[nxt])
      sort_top(nxt);
    }
    S.push_back(node);
}


void DFS(int x, vector<int> G[], int comp_cur)
{
     comp[x] = comp_cur;
     for(auto i : G[x])
        if(comp[i] == 0)
          DFS(i, G, comp_cur);
    
}
int main()
{
  f >> N >> M;
  while(M--)
  {
    int a, b;
    f >> a >> b;
    G[a].push_back(b);
    Gt[b].push_back(a);
  }
  for(int i = 1; i <= N; ++i)
  {
    if(!vis[i])
    {
        sort_top(i);
    }
  }
  reverse(S.begin(), S.end());
  memset(vis, 0, sizeof(vis));
  int num_comp = 0;
  for(auto s : S)
  {
    if(comp[s] == 0)
    {
        DFS(s, Gt, ++num_comp);
    }
  }
  

  vector<vector<int>> comps(num_comp);
  for(int i = 1; i <= N; ++i)
  {
    comps[comp[i] - 1].push_back(i);

  }
   

  g << num_comp << '\n';
  for(auto i : comps)
  {
    for(auto j : i)
    {
        g << j << " ";
    }
    g << '\n';
  }

  return 0;

}