Cod sursa(job #2450110)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 21 august 2019 22:38:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int NT = 100000 + 7;
int n, m;
vector <int> g1[NT];
vector <int> g2[NT];
int ord[NT], top;
bool jeg[NT];

void ju(int nod) {
 jeg[nod] = 1;
 for(auto &nou : g1[nod])
  if(jeg[nou] == 0)
   ju(nou);
 ord[++top] = nod;
}

vector <int> uc;
void jo(int nod) {
 jeg[nod] = 1;
 uc.push_back(nod);
 for(auto &bou : g2[nod])
  if(jeg[bou] == 0)
   jo(bou);
}

int main() {
 freopen("ctc.in", "r", stdin),
         freopen("ctc.out", "w", stdout);

 scanf("%d%d", &n, &m);
 for(int i = 1; i <= m; i++) {
  int a, b;
  scanf("%d%d", &a, &b);
  g1[a].push_back(b);
  g2[b].push_back(a);
 }

 vector <vector <int>> luv;

 for(int i = 1; i <= n; i++)
  if(jeg[i] == 0)
   ju(i);
 for(int i = 1; i <= n; i++)
  jeg[i] = 0;
 for(int i = n; i >= 1; i--)
  if(jeg[ord[i]] == 0) {
   uc.clear();
   jo(ord[i]);
   luv.push_back(uc);
  }
 cout << (int)luv.size() << "\n";
 for(auto &x : luv) {
  for(auto &y : x)
   cout << y << " ";
  cout << "\n";
 }

 return 0;
}