Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <list>
- using namespace std;
- class Graph {
- public:
- Graph(int V): vert(V) {}~Graph() {}
- void addEdge(int u, int v) { adj[u].push_back(v); }
- const list<int> & edges(int u) const { return adj[u]; }
- bool cycle(vector < int > & path) const{// a(v) < a(u) < t(u) < t(v) // u->v
- dfs(p,A,T);
- for(int w:A){
- for(int k:A){
- if (A[k]<A[w]<T[w]<T[k]){
- for(int l:p){
- if(p[l]==w)
- }
- return true;
- }
- }
- }
- }
- private:
- vector<list<int>> adj;
- int vert;
- enum state {UNVISITED, SEEN, VISITED};
- vector<int> p,A,T;
- void dfs_help(int u, int & time,vector < int > & p,
- vector < int > & A, vector < int > & T,
- vector < state > & status) {
- status[u] = SEEN;
- A[u] = ++time;
- for (int v: edges(u))
- if (status[v] == UNVISITED) {
- p[v] = u;
- dfs_help(v, time, p, A, T, status);
- }
- status[u] = VISITED;
- T[u] = ++time;
- }
- void dfs(vector < int > & p,
- vector < int > & A, vector < int > & T) {
- int N = vert;
- vector < state > status(N);
- for (int u = 0; u < N; ++u) {
- p[u] = -1;
- status[u] = UNVISITED;
- }
- int time = 0;
- for (int u = 0; u < N; ++u)
- if (status[u] == UNVISITED)
- dfs_help(u, time, p, A, T, status);
- }
- };
- int main() {
- int V, E;
- cin >> V >> E;
- Graph g(V);
- for (int i = 0; i < E; ++i) {
- int u, v;
- cin >> u >> v;
- g.addEdge(u, v);
- }
- vector < int > path;
- bool c = g.cycle(path);
- if (c) {
- cout << "CYCLE:";
- for (int i = 0; i < path.size(); ++i)
- cout << path[i] << (i == path.size() - 1 ? "\n" : "");
- } else {
- cout << "NO CYCLE" << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement