fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 105;
  5. vector<int> ke[MAXN], keNguoc[MAXN];
  6. bool daTham[MAXN];
  7. stack<int> thuTuDinh;
  8. vector<vector<int>> thanhPhanLienThongManh;
  9. int soDinh, soCanh;
  10.  
  11. void dfs1(int u) {
  12.     daTham[u] = true;
  13.     for (int v : ke[u]) {
  14.         if (!daTham[v]) dfs1(v);
  15.     }
  16.     thuTuDinh.push(u);
  17. }
  18.  
  19. void dfs2(int u, vector<int>& thanhPhan) {
  20.     daTham[u] = true;
  21.     thanhPhan.push_back(u);
  22.     for (int v : keNguoc[u]) {
  23.         if (!daTham[v]) dfs2(v, thanhPhan);
  24.     }
  25. }
  26.  
  27. void timThanhPhanLienThongManh() {
  28.     fill(daTham, daTham + soDinh + 1, false);
  29.     for (int i = 1; i <= soDinh; i++) {
  30.         if (!daTham[i]) dfs1(i);
  31.     }
  32.  
  33.     fill(daTham, daTham + soDinh + 1, false);
  34.     while (!thuTuDinh.empty()) {
  35.         int u = thuTuDinh.top(); thuTuDinh.pop();
  36.         if (!daTham[u]) {
  37.             vector<int> thanhPhan;
  38.             dfs2(u, thanhPhan);
  39.             sort(thanhPhan.begin(), thanhPhan.end());
  40.             thanhPhanLienThongManh.push_back(thanhPhan);
  41.         }
  42.     }
  43.     sort(thanhPhanLienThongManh.begin(), thanhPhanLienThongManh.end());
  44. }
  45.  
  46. int main() {
  47.     cin >> soDinh >> soCanh;
  48.     for (int i = 0; i < soCanh; i++) {
  49.         int u, v;
  50.         cin >> u >> v;
  51.         ke[u].push_back(v);
  52.         keNguoc[v].push_back(u);
  53.     }
  54.  
  55.     timThanhPhanLienThongManh();
  56.  
  57.     cout << thanhPhanLienThongManh.size() << "\n";
  58.     for (const auto& tp : thanhPhanLienThongManh) {
  59.         for (int dinh : tp) cout << dinh << " ";
  60.         cout << "\n";
  61.     }
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 5292KB
comments ()
stdin
copy 
6 7
1 2
1 4
2 3
3 1
4 5
5 6
6 1
stdout
copy 
1
1 2 3 4 5 6
https://ideone.com/O4ndgr
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!