Depth first search(DFS)

[1vf9z8AR]

Problem-
https://www.spoj.com/problems/PT07Y/

Issue-
getting wrong answer on spoj but test cases are getting the right output.

My technique-
check if each node visited
check if cycle is present.

if cycle present or each node not visited then it is not a tree.

  // adj is for adjacent nodes
//visited is to check if visited or not
// parent is parent node
//prev is previous node
//current is current node
#include<iostream>
#include<vector>
using namespace std;
bool cycle(vector<int>adj[],bool visited[],int parent,int prev,int current)
{
    if(visited[current]==true && current!=parent)
    {
        return true;
    }
        for(auto x:adj[current])
        {
            visited[current]=true;
            if(x!=prev)
                cycle(adj,visited,prev,current,x);
        }
}
int main()
{
    int n,m;
    cin>>n>>m;
    if(n!=m+1)
    {
        cout<<"NO";
        return 0;
    }
    bool hascycle=false;
    vector<int>adj[n+1];
    int t1,t2;
    vector<int>node;
    for(int i=0;i<m;i++)
    {
        cin>>t1>>t2;
        adj[t1].push_back(t2);
        adj[t2].push_back(t1);
        node.push_back(t1);
        node.push_back(t2);
    }
    bool visited[n+1];
    for(auto x:node)
    {
        visited[x]=false;
    }
    hascycle=cycle(adj,visited,1,1,1);
   for(auto x:node)
    {
        if(visited[x]==false)
        {
            cout<<"NO";
            return 0;
        }
    }
    if(hascycle==true)
        cout<<"NO";
    else
        cout<<"YES";
    return 0;
}

hascycle stores the condition if cycle exists or not.
node stores all nodes.

[ne555]

In function ‘bool cycle(std::vector<int>*, bool*, int, int, int)’:
warning: control reaches end of non-void function [-Wreturn-type]

and a testcase

2 1
1 1

also, `visited[1]' may remain uninitialised but you'll try to access it on cycle()

[1vf9z8AR]

@ne555
thanks, it got accepted.

I can't believe it, codeblocks will give me "yes" and the online compiler will give me "no" :|

after adding return false; to end of cycle() problem was fixed.

[MikeyBoy]

Different compilers can give different warnings. Especially if they're using different options for their warning levels.

As a general rule, it's best to tell your compiler to show you as many warnings as possible. Because why wouldn't you want it to point out things in your code that need fixing?

[1vf9z8AR]

ok.