determine if an undirected graph is a tree using map

[BaseRev]

Hi all,

I tried to check if an undirected graph is a tree using std::map container , I

have number of nodes in the graph(n) and number of edges(m) and every link

between two nodes.

so I tried the following but it appears to be wrong (as I tested it on this

similar problem on SPOJ http://www.spoj.com/problems/PT07Y/) and I don't know

why ,so if anyone can tell me what is wrong with this it would be great,Thanks.

#include <iostream>
#include <map>

using namespace std;

int main()
{
    map<int,int> Links;
    int n,m,Parent,Child;

    cin>>n>>m;
    if(m!=n-1) //First Condition: Number of Links=Number of Nodes-1 
    {
        cout<<"NO"<<endl;
        return 0;
    }
    while(m!=0)
    {
        m--;
        cin>>Parent>>Child;


        if(Links[Child]!=0)
        {
            if(Links[Parent]!=0) //No node has more than one parent
            {
                cout<<"NO"<<endl;
                return 0;
            }
            Links[Parent]=Child;
        }
        else
        Links[Child]=Parent;

    }
    cout<<"YES"<<endl;

    return 0;
}

[ne555]

undirected graph
//No node has more than one parent ¿parent? ¿how do you know which one is the parent?

[MiiNiPaa]

I believe you need this: start with random node and start to recursively traverse all connected nodes. After you went into neighbour node, delete link you came from from all link list (to avoid returns). Check if node in visited list (or map<node, bool>). If it is, then there is a loop and graph is not a tree. If it isn't add it to visited list (set map[node] to true). Continue traversal. If you went over all connections, and there is no loops check if all nodes were visited. If is, then it is a tree, otherwise there is freestanding nodes and it isn't a tree.

[BaseRev]

how do you know which one is the parent?

Well,I don't but since all I need is to check if the graph is a tree I choose one of the two nodes as a parent and the other as a child and that wouldn't change the fact whether it is a tree or not it just changes the tree shape.

@MiiNiPaa
I think that the problem is when there is a loop and separated nodes in the graph. It can't detect them I tried input like :
5 4
1 2
3 1
2 4
4 3
which is a graph with a loop and separated node and it output "YES"
but if I entered it that way it output "NO":
5 4
1 2
1 3
2 4
3 4
so generally, I need to check for cuts in the graph .

Thanks for both replies . I now know what is the problem .

[BaseRev]

I changed the idea to this and now it works as expected :

#include <iostream>
#include <map>

using namespace std;

int main()
{
    map<int,bool> Links;
    int n,m,N1,N2;

    cin>>n>>m;
    if(m!=n-1) //First Condition: Number of Links=Number of Nodes-1 
    {
        cout<<"NO"<<endl;
        return 0;
    }
    while(m!=0)
    {
        m--;
        cin>>N1>>N2;

        if(Links[N1] && Links[N2]) //Asumming the graph is given as it builds
        {
            cout<<"NO"<<endl;
            return 0;
        }
       Links[N1]=1;
       Links[N2]=1;
    }


    cout<<"YES"<<endl;

    return 0;
}

I now need to change it to account for cases when the graph is given like this :
4 3
1 2
3 4
1 3