fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int NMAX = 15;
  6.  
  7. struct node {
  8.     int info;
  9.     node* next;
  10. };
  11.  
  12. void add(node* &first, int val) {
  13.     node* p = new node;
  14.     p -> info = val;
  15.     p -> next = first;
  16.     first = p;
  17. }
  18.  
  19. void read(int& n, int& m, node* G[NMAX], node* Gt[NMAX]) {
  20.     cin >> n >> m;
  21.     for (int i = 1; i <= m; ++ i) {
  22.         int x, y;
  23.         cin >> x >> y;
  24.         add(G[x], y);
  25.         add(Gt[y], x);
  26.     }
  27. }
  28.  
  29. void dfs1(node* G[NMAX], int currNode, bool seen[NMAX], int stck[NMAX], int& dim) {
  30.     seen[currNode] = true;
  31.     for (node* p = G[currNode]; p; p = p -> next)
  32.         if (!seen[p -> info])
  33.             dfs1(G, p -> info, seen, stck, dim);
  34.     stck[++ dim] = currNode;
  35. }
  36.  
  37. void dfs2(node* Gt[NMAX], int currNode, bool seen[NMAX], int idx) {
  38.     seen[currNode] = true;
  39.     // prelucrare nodul cnt din componenta idx
  40.     cout << currNode << " ";
  41.     for (node* p = Gt[currNode]; p; p = p -> next)
  42.         if (!seen[p -> info])
  43.             dfs2(Gt, p -> info, seen, idx);
  44. }
  45.  
  46. void solve(int n, node* G[NMAX], node* Gt[NMAX]) {
  47.     bool seen[NMAX];
  48.     int stck[NMAX], dim = 0;
  49.     for (int i = 1; i <= n; ++ i)
  50.         seen[i] = false;
  51.     for (int i = 1; i <= n; ++ i)
  52.         if (!seen[i])
  53.             dfs1(G, i, seen, stck, dim);
  54.  
  55.     int idx = 0;
  56.     for (int i = 1; i <= n; ++ i)
  57.         seen[i] = false;
  58.     while (dim) {
  59.         if (!seen[stck[dim]]) {
  60.             ++ idx;
  61.             cout << idx << " ";
  62.             dfs2(Gt, stck[dim], seen, idx);
  63.             cout << "\n";
  64.         }
  65.         -- dim;
  66.     }
  67. }
  68.  
  69. int main() {
  70.     int n, m;
  71.     node* G[NMAX];
  72.     node* Gt[NMAX];
  73. 	read(n, m, G, Gt);
  74. 	solve(n, G, Gt);
  75. 	return 0;
  76. }
  77.  
Runtime error #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
6 7
1 2
2 1
2 3
3 4
4 5
5 6
6 4
stdout
copy 
Standard output is empty
https://ideone.com/zHRwLz
language:
C++14 (gcc 8.3)
created:
7 years 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!