Advertisement
Ser1ousSAM

tamp

Oct 17th, 2020
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. void dfs(int v, vector <int> &visited, vector<vector<int>> &graph) {
  5.     visited[v] = 1; // отмечаем, что вошли в вершину
  6.     for (int u=graph[v]; i < graph[v]; i++) { // перебираем всех соседей
  7.             if (visited[u]==) {
  8.                 // если сосед еще не посещен, запускаем из него обход
  9.                 if (visited[i] == 0)
  10.                 Color.White->dfs(u)
  11.                     // если сосед на пути от корня до текущей, то мы нашли цикл
  12.                     Color.Grey->TODO("Вывести цикл")
  13.             }
  14.         }
  15.  
  16.     visited[v] = 2; // отмечаем, что вышли из вершины
  17. }
  18. int main() {
  19.     int n, m;
  20.     vector<vector<int>> graph;
  21.     int u, v;
  22.     for (int i = 0; i < m; i++)
  23.     {
  24.         cin >> u >> v;
  25.         u--;
  26.         v--;
  27.         graph[u].push_back(v);//vector
  28.     }
  29.     vector <int> visited(n, 0);// массив из n значений Color.White (0)
  30.     int n = graph.size();
  31.     for (int i = 0; i < n; i++) { // перебираем все вершины
  32.         if (visited[i] == 0) {
  33.             dfs(i, visited, graph); // от каждой еще не посещенной запускаем dfs
  34.         }
  35.     }
  36.     return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement