Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <optional>
- #include <unordered_set>
- #include <vector>
- enum class Color {
- WHITE = 0,
- GREY = 1,
- BLACK = 2,
- };
- class Graph {
- public:
- explicit Graph(int vertices_amount) : graph_(vertices_amount) {}
- void AddEdge(int from, int to) {
- graph_[from].insert(to);
- graph_[to].insert(from);
- }
- const std::unordered_set<int>& GetVerticesList(int vertice) const {
- return graph_[vertice];
- }
- size_t GetVerticesAmount() const {
- return graph_.size();
- }
- private:
- std::vector<std::unordered_set<int>> graph_;
- };
- struct Visitor {
- std::vector<Color> used;
- std::vector<int> parent;
- int cycle_start = -1;
- int cycle_end = -1;
- Visitor(int vertices_amount) : used(vertices_amount, Color::WHITE), parent(vertices_amount, -1) {}
- };
- bool DFS(const Graph& graph, Visitor& visitor, int vertice, int par = -1) {
- visitor.used[vertice] = Color::GREY;
- for (int other_vertice: graph.GetVerticesList(vertice)) {
- if (other_vertice == par) {
- continue;
- }
- if (visitor.used[other_vertice] == Color::WHITE) {
- visitor.parent[other_vertice] = vertice;
- if (DFS(graph, visitor, other_vertice, vertice)) {
- return true;
- }
- }
- else if (visitor.used[other_vertice] == Color::GREY) {
- visitor.cycle_end = vertice;
- visitor.cycle_start = other_vertice;
- return true;
- }
- }
- visitor.used[vertice] = Color::BLACK;
- return false;
- }
- int main() {
- int vertices_amount;
- std::cin >> vertices_amount;
- Graph graph(vertices_amount);
- for (int i = 0; i < vertices_amount; ++i) {
- for (int j = 0; j < vertices_amount; ++j) {
- int number;
- std::cin >> number;
- if (number == 1) {
- graph.AddEdge(i, j);
- }
- }
- }
- Visitor visitor(vertices_amount);
- for (int i = 0; i < vertices_amount; ++i) {
- if (DFS(graph, visitor, i)) {
- std::cout << "YES\n";
- std::vector<int> cycle;
- for (int vertice = visitor.cycle_end; vertice != visitor.cycle_start; vertice = visitor.parent[vertice]) {
- cycle.push_back(vertice);
- }
- cycle.push_back(visitor.cycle_start);
- std::reverse(cycle.begin(), cycle.end());
- std::cout << cycle.size() << "\n";
- for (auto vertice: cycle) {
- std::cout << vertice + 1 << " ";
- }
- return 0;
- }
- }
- std::cout << "NO";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment