Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <stdlib.h>
- #include <stdio.h>
- #include <vector>
- #include <queue>
- using namespace std;
- vector< vector<int> > G;
- vector<int> used;
- vector<int> answ;
- int flag = 0;
- int start;
- void DFS (int v) {
- printf("v = %d\n", v);
- used[v] = 1; // 1 - gray 2 - black
- for (int i = 0; i < G[v].size(); i++) {
- if (flag == 1) {
- answ.push_back(v + 1);
- printf("continue\n");
- return;
- }
- int to = G[v][i];
- printf("to = %d \n", to);
- if (used[to] == 1) {
- start = to;
- printf("RAISE FLAG curr %d start %d\n", v, start );
- flag = 1;
- break;
- } else {
- if (used[to] == 0) DFS (to);
- }
- }
- used[v] = 2;
- if (flag == 1) {
- printf("curr %d start %d\n",v , start );
- printf("PUSH\n" );
- answ.push_back(v + 1);
- }
- }
- void topsort(int V) {
- for (int i=0; i < V; ++i) {
- if (!used[i] && !flag) {
- printf("START DFS (%d)\n", i);
- DFS (i);
- }
- }
- }
- int main() {
- ifstream fin("cycle.in");
- ofstream fout("cycle.out");
- int V, E;
- fin >> V >> E;
- G.resize(V);
- used.resize(V, 0);
- int i, j, x, y;
- for (i = 0; i < E; i++) {
- fin >> x >> y;
- G[x-1].push_back(y-1);
- }
- topsort(V);
- if (!flag) {
- fout << "NO";
- } else {
- fout << "YES" << endl;
- for (int i = 0; i < answ.size(); i++) {
- fout << answ[i] << ' ';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement