Advertisement
Guest User

fucdfs

a guest
Jan 18th, 2019
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class graph
  7. {
  8. public:
  9.     vector<vector<int>> G;
  10.     int n;
  11.     graph()
  12.     {
  13.         cin >> n;
  14.         color = new int[n];
  15.         parent = new int[n];
  16.         for (int i = 0; i < n; i++)
  17.         {
  18.             color[i] = 0;
  19.             parent[i] = -1;
  20.         }
  21.     }
  22.     void dfs(int v, int p, int b) {
  23.         if (color[v])
  24.         {
  25.             if (v == parent[parent[v]])
  26.             {
  27.                 return; // вершина уже посещена, уходим
  28.             }
  29.             find();
  30.         }
  31.         parent[v] = p; // сохраняем, откуда пришли
  32.         color[v] = 1;  // помечаем вершину серой
  33.         //if (v==b&&b!=parent[v]) find();
  34.        
  35.         for (int i = 0; i < G[v].size(); ++i)
  36.         {
  37.             // пробуем пойти во все смежные вершины
  38.             dfs(G[v][i], v, b);
  39.         }
  40.         color[v] = 2; // помечаем вершину чёрной
  41.     }
  42. private:
  43.     int *color, *parent;
  44.     int find()
  45.     {
  46.         cout << "NO";
  47.         return 0;
  48.     }
  49. };
  50.  
  51. int main()
  52. {
  53.     graph derevo;
  54.     int buf;
  55.     for (int i = 0; i < derevo.n; i++)
  56.     {
  57.         derevo.G.resize(derevo.n);
  58.         for (int q = 0; q < derevo.n; q++)
  59.         {
  60.             cin >> buf;
  61.             if (buf == 1)
  62.             {
  63.                 derevo.G[i].push_back(i);
  64.             }
  65.         }
  66.     }
  67.     for (int i = 0; i < derevo.n; i++)
  68.     {
  69.         for (int q = 0; q < derevo.G[i].size(); q++)
  70.         {
  71.             derevo.dfs(derevo.G[i][q], i, i);
  72.         }
  73.     }
  74.     cout << "YES";
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement