Захваты: обнаружив цикл на неориентированном графике, как его распечатать? - PullRequest
Новая
       92

Захваты: обнаружив цикл на неориентированном графике, как его распечатать?

0 голосов
/ 14 июля 2020

I wi sh для обнаружения и печати цикла (любой 1, если их много) в неориентированном графе. Код DFS, который я написал ниже, определяет наличие цикла, а также находит вершину внутри цикла. Как мне продолжить печать цикла? Должен ли я изменить свой код DFS или поиграть с вершиной цикла в отдельном коде? 

    int n,m,x,y,a,cycle=0,flag=0;
    cin>>n>>m;
    vector<int>adj[n+1];
    for(int i=0;i<m;i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<bool>vis(n+1,false);
    vector<int>parent(n+1,0);
    stack<int>s;
    for(int i=1;i<=n  && flag!=1;i++){
        if(vis[i])
            continue;
        else{
            vis[i]=true;
            s.push(i);
            while(!s.empty() && flag!=1){
                a=s.top();
                s.pop();
                for(auto neighbors : adj[a]){
                    if(vis[neighbors]){
                        if(neighbors!=parent[a]){
                            flag=1;
                            cycle=neighbors; // stores a vertex of the detected cycle 
                            break;
                        }
                    }
                    else{
                        vis[neighbors]=true;
                        s.push(neighbors);
                        parent[neighbors]=a;
                    }
                }
            }
        }
    }

Я долго думал, но не смог найти способ правильно распечатать цикл .

...