fork download
copy 
  1. #pragma GCC diagnostic ignored "-Wunused-parameter"
  2. #define _USE_MATH_DEFINES
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define INP "solve"
  8. #define OUT "solve"
  9.  
  10. const long long INF_LL = 1e17;
  11. const int INF = 1e9 + 100;
  12. const int MOD = 1e9 + 7;
  13. const int Base = 311;
  14. const long double EPS = 1e-10;
  15. const int BLOCK = 1000;
  16. const int dx[4] = {0, 0, 1, -1};
  17. const int dy[4] = {1, -1, 0, 0};
  18. mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
  19.  
  20. void open_file() {
  21.     #ifdef THEMIS
  22.         freopen(INP ".inp","r",stdin);
  23.         freopen(OUT ".out","w",stdout);
  24.     #endif // THEMIS
  25. }
  26.  
  27. const int maxN = 5e5 + 100;
  28.  
  29. int in_deg[maxN];
  30. vector<int> adj[maxN];
  31. int n, m;
  32. //n = |V|, m = |E|
  33. void readGraph() {
  34.     cin >> n >> m;
  35.     //n = |V|, m = |E|
  36.     for (int i = 0; i < m; i++) {
  37.         int u, v;
  38.         cin >> u >> v;
  39.         adj[u].push_back(v);
  40.         in_deg[v]++;
  41.     }
  42.     for (int u = 0; u < n; u++) {
  43.         cout << "adj(" << u << "): ";
  44.         for (int v : adj[u]) {
  45.             cout << v << ' ';
  46.         }
  47.         cout << '\n';
  48.     }
  49.     cout << '\n';
  50. }
  51.  
  52. int used[maxN]; //Kiểm tra đỉnh u đã thăm hay chưa ?
  53. vector<int> T;
  54. void topo_DFS(int u) {
  55.     used[u] = 1;
  56.     for (int v : adj[u]) {
  57.         if (used[v] == 0) {
  58.             topo_DFS(v);
  59.         }
  60.     }
  61.     T.push_back(u);
  62. }
  63.  
  64. void topo_BFS() {
  65.     queue<int> Q;
  66.     for (int i = 0; i < n; i++) {
  67.         if (in_deg[i] == 0) {
  68.             Q.push(i);
  69.         }
  70.     }
  71.     assert((int)Q.size() > 0); ///Chắc chắn tồn tại đỉnh có bậc vào = 0
  72.     int idQ = 0;
  73.     while ((int)Q.size() != 0) {
  74.         {
  75.             ///Dùng để in thử, các bạn không cần quan tâm phần này
  76.             vector<int> vertice;
  77.             while ((int)Q.size() != 0) {
  78.                 int u = Q.front(); Q.pop();
  79.                 vertice.push_back(u);
  80.             }
  81.             cout << "Queue " << idQ << ": " << '\n';
  82.             for (int u : vertice) {
  83.                 cout << u << ' ';
  84.                 Q.push(u);
  85.             }
  86.             cout << '\n';
  87.             idQ++;
  88.         }
  89.         int u = Q.front(); Q.pop();
  90.         T.push_back(u);
  91.         for (int v : adj[u]) {
  92.             --in_deg[v];
  93.             if (in_deg[v] == 0) {
  94.                 Q.push(v);
  95.             }
  96.         }
  97.     }
  98.  
  99. }
  100. void sol() {
  101.     readGraph();
  102.     {
  103.         for (int i = 0; i < n; i++) used[i] = 0;
  104.         T.clear();
  105.         for (int i = 0; i < n; i++) { //Có thể là một hoán vị của n
  106.             if (used[i] == 0) {
  107.                 topo_DFS(i);
  108.             }
  109.         }
  110.         reverse(T.begin(), T.end());
  111.         cout << "Thu tu topo sort voi DFS: " << '\n';
  112.         for (int u : T) cout << u << ' ';
  113.         cout << '\n';
  114.         cout << '\n';
  115.     }
  116.     {
  117.         T.clear();
  118.         topo_BFS();
  119.         cout << "Thu tu topo sort voi BFS: " << '\n';
  120.         for (int u : T) cout << u << ' ';
  121.         cout << '\n';
  122.     }
  123. }
  124.  
  125. void solve() {
  126.     int T;
  127.     //cin >> T;
  128.     T = 1;
  129.     int TestCase = 0;
  130.     while (T--) {
  131.         TestCase += 1;
  132.         //cout << "Case #" << TestCase << ":" << ' ';
  133.         ///cout << "Case #" << TestCase << '\n';
  134.         //cout << "Test " << TestCase << ": ";
  135.         sol();
  136.     }
  137. }
  138. int main(int argc,char *argv[]) {
  139.     ///srand(time(nullptr));
  140.     ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
  141.     open_file();
  142.     solve();
  143. }
  144.  
Success #stdin #stdout 0.01s 15448KB
comments (?)
stdin
copy 
5 6
3 0
3 1
0 1
0 4
4 2
1 2
stdout
copy 
adj(0): 1 4 
adj(1): 2 
adj(2): 
adj(3): 0 1 
adj(4): 2 

Thu tu topo sort voi DFS: 
3 0 4 1 2 

Queue 0: 
3 
Queue 1: 
0 
Queue 2: 
1 4 
Queue 3: 
4 
Queue 4: 
2 
Thu tu topo sort voi BFS: 
3 0 1 4 2
https://ideone.com/vL1khL
language:
C++14 (gcc 8.3)
created:
3 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!