Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::vector;
- void DFS(int v, int p, vector<vector<int>>& neighbours, vector<std::string>& colour, vector<int>& parent, bool& flag) {
- parent[v] = p;
- colour[v] = "GREY";
- for (int to : neighbours[v]) {
- if (flag) {
- break;
- }
- if (colour[to] == "BLACK") {
- continue;
- }
- if (colour[to] == "GREY") {
- std::cout << "YES\n";
- flag = true;
- vector<int> cycle;
- int u = v;
- while (u != to) {
- cycle.push_back(u + 1);
- u = parent[u];
- }
- cycle.push_back(to + 1);
- for (int i = cycle.size() - 1; i >= 0; --i) {
- std::cout << cycle[i] << " ";
- }
- colour[v] = "BLACK";
- return;
- }
- DFS(to, v, neighbours, colour, parent, flag);
- }
- colour[v] = "BLACK";
- }
- int main() {
- int n, m;
- std::cin >> n >> m;
- vector<vector<int>> neighbours(n);
- vector<std::string> colour(n, "WHITE");
- vector<int> parent(n);
- for (int j = 0; j < m; ++j) {
- int l, r;
- std::cin >> l >> r;
- neighbours[l - 1].push_back(r - 1);
- }
- bool flag = false;
- for (int i = 0; i < n; ++i) {
- if (colour[i] == "WHITE") {
- DFS(i, -1, neighbours, colour, parent, flag);
- if (flag) {
- break;
- }
- }
- }
- if (!flag) {
- std::cout << "NO";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement