Cod sursa(job #2899874)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 14:36:45
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>

bool home = 1;
using namespace std;

const string TASKNAME="ctc";
const int N=100000+7;
int n;
int m;
bool vis[N];
vector<int> g[N];
vector<int> ig[N];
vector<int> ord;

void dfs(int a) {
  if (vis[a]) return;
  vis[a]=1;
  for (auto &b:g[a]) {
    dfs(b);
  }
  ord.push_back(a);
}

vector<int> cur;

void invdfs(int a) {
  if(vis[a]) return;
  vis[a]=1;
  cur.push_back(a);
  for (auto &b:ig[a]) {
    invdfs(b);
  }
}

signed main() {
#ifdef INFOARENA
  home = 0;
#endif

  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }

  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++) {
    int a,b;
    scanf("%d%d",&a,&b);
    g[a].push_back(b);
    ig[b].push_back(a);
  }
  for (int i=1;i<=n;i++) {
    dfs(i);
  }
  reverse(ord.begin(),ord.end());
  for (int i=1;i<=n;i++) {
    vis[i]=0;
  }
  vector<vector<int>> sol;
  for (int i=1;i<=n;i++) {
    if(vis[i]) continue;
    cur.clear();
    invdfs(i);
    sol.push_back(cur);
  }
  printf("%d\n",(int)sol.size());
  for (auto &v:sol) {
    for (auto &x:v) {
      printf("%d ", x);
    }
    printf("\n");
  }
}