Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class graph
- {
- public:
- vector<vector<int>> G;
- int n;
- graph()
- {
- cin >> n;
- color = new int[n];
- parent = new int[n];
- for (int i = 0; i < n; i++)
- {
- color[i] = 0;
- parent[i] = -1;
- }
- }
- void dfs(int v, int p, int b) {
- if (color[v])
- {
- if (v == parent[parent[v]])
- {
- return; // вершина уже посещена, уходим
- }
- find();
- }
- parent[v] = p; // сохраняем, откуда пришли
- color[v] = 1; // помечаем вершину серой
- //if (v==b&&b!=parent[v]) find();
- for (int i = 0; i < G[v].size(); ++i)
- {
- // пробуем пойти во все смежные вершины
- dfs(G[v][i], v, b);
- }
- color[v] = 2; // помечаем вершину чёрной
- }
- private:
- int *color, *parent;
- int find()
- {
- cout << "NO";
- return 0;
- }
- };
- int main()
- {
- graph derevo;
- int buf;
- for (int i = 0; i < derevo.n; i++)
- {
- derevo.G.resize(derevo.n);
- for (int q = 0; q < derevo.n; q++)
- {
- cin >> buf;
- if (buf == 1)
- {
- derevo.G[i].push_back(i);
- }
- }
- }
- for (int i = 0; i < derevo.n; i++)
- {
- for (int q = 0; q < derevo.G[i].size(); q++)
- {
- derevo.dfs(derevo.G[i][q], i, i);
- }
- }
- cout << "YES";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement