CODEWITHSUNDEEP
algorithmgraphdepth-first-search
user4822631
user4822631

Reputation:

DFS algorithm to detect cycles in graph

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph{
        public:
            vector<int> adjList[10001];
            void addEdge(int u,int v){
                adjList[u].push_back(v);
                adjList[v].push_back(u);
            }
};

bool dfs(Graph graph, int n){
    vector<int> neighbors;
    int curr,parent;
    bool visited[10001] = {0};
    stack<int> s;
    //Depth First Search
    s.push(1);
    parent = 0;
    while(!s.empty()){
        curr = s.top();
        neighbors = graph.adjList[curr];
        s.pop();
        //If current is unvisited
        if(visited[curr] == false){
            for(int j=0; j<neighbors.size(); j++){
                //If node connected to itself, then cycle exists
                if(neighbors[j] == curr){
                    return false;;
                }
                else if(visited[neighbors[j]] == false){
                    s.push(neighbors[j]);
                }
                //If the neighbor is already visited, and it is not a parent, then cycle is detected
                else if(visited[neighbors[j]] == true && neighbors[j] != parent){
                    return false;
                }
            }
            //Mark as visited
            visited[curr] = true;
            parent = curr;
        }
    }
    //Checking if graph is fully connected
    for(int i=1; i<=n; i++){
        if(visited[i] == false){
            return false;
        }
    }
    //Only if there are no cycles, and it's fully connected, it's a tree
    return true;
}

int main() {
    int m,n,u,v;
    cin>>n>>m;
    Graph graph = Graph();
    //Build the graph
    for(int edge=0; edge<m; edge++){
        cin>>u>>v;
        graph.addEdge(u,v);
    }
    if(dfs(graph,n)){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
    return 0;
}

I am trying to determine if a given graph is a tree.

I perform DFS and look for cycles, if a cycle is detected, then the given graph is not a tree.

Then I check if all nodes have been visited, if any node is not visited, then given graph is not a tree

The first line of input is: n m Then m lines follow, which represent the edges connecting two nodes

n is number of nodes m is number of edges

example input:
3 2
1 2
2 3

This is a SPOJ question http://www.spoj.com/problems/PT07Y/ and I am getting Wrong Answer. But the DFS seems to be correct according to me.

Upvotes: 0

Views: 542

Answers (1)

Tomasz Plaskota
Tomasz Plaskota

Reputation: 1367

So I checked your code against some simple test cases in comments, and it seems that for

7 6
3 1
3 2
2 4
2 5
1 6
1 7

you should get YES as answer, while your program gives NO.

This is how neighbours looks like in this case:

1: 3 6 7 
2: 3 4 5 
3: 1 2 
4: 2 
5: 2 
6: 1 
7: 1

So when you visit 1 you push 3,6,7 on the stack. Your parent is set as 1. This is all going good.

You pop 7 from the stack, you don't push anything on the stack and cycle check clears out, so as you exit while loop you set visited[7] as true and set you parent to 7 (!!!!!).

Here is you can see this is not going well, since once you popped 6 from the stack you have 7 saved as parent. And it should be 1. This makes cycle check fail on neighbor[0] != parent.

I'd suggest adding keeping parent in mapped array and detect cycles by applying union-merge.

Upvotes: 0

Related Questions