fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100;
  5. vector<int> adj[MAXN];   // danh sách kề
  6. bool visited[MAXN];
  7. bool found = false;
  8. int n;
  9.  
  10. // DFS kiểm tra có đường đi từ u đến v hay không
  11. void dfs(int u, int v) {
  12.     if (u == v) {
  13.         found = true;
  14.         return;
  15.     }
  16.  
  17.     visited[u] = true;
  18.  
  19.     for (int x : adj[u]) {
  20.         if (!visited[x]) {
  21.             dfs(x, v);
  22.         }
  23.     }
  24. }
  25.  
  26. int main() {
  27.     n = 5;
  28.  
  29.     //tạo input danh sách cạnh (edge list) cho mục đích demo
  30.     vector<pair<int,int>> edges = {
  31.         {0, 1},
  32.         {1, 2},
  33.         {0, 3},
  34.         {3, 4},
  35.         {4, 2}
  36.     };
  37.  
  38.     // xây dựng danh sách kề: mỗi đỉnh u có 1 list những đỉnh kề với nó (có cạnh nối tới u)
  39.     for (auto e : edges) {
  40.         int u = e.first;
  41.         int v = e.second;
  42.         adj[u].push_back(v);
  43.         adj[v].push_back(u); // đồ thị vô hướng nên ta push cả u vào danh sách kề của v
  44.     }
  45.  
  46.     int u = 0, v = 2; //demo tìm đường đi từ đỉnh 0 đến 2
  47.  
  48.     memset(visited, false, sizeof(visited));
  49.     dfs(u, v);
  50.  
  51.     if (found)
  52.         cout << "Co duong di tu " << u << " den " << v << endl;
  53.     else
  54.         cout << "Khong co duong di tu " << u << " den " << v << endl;
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Co duong di tu 0 den 2
https://ideone.com/ptfmgC
Code demo DFS. Bài toán xác định có đường đi từ u đến v không
language:
C++14 (gcc 8.3)
created:
7 hours 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!