0

问题：我得到一个无向图，其中包含节点计数（n）、边数（m）和节点之间的边。我需要使用std::map确定它是否是一棵树。

输入将是这样的：nm

然后 m 行描述节点之间的边

所以我尝试了以下方法：

#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 -> No loops && No Cuts
    {
        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;
}

但它只是产生错误的答案，我不知道为什么（我在这个在线法官的问题上测试过A similar question on SPOJ）

任何帮助将不胜感激，谢谢。

4

1 回答 1

0

好吧，我发现出了什么问题。

问题是当图中存在循环和分离节点时。它无法检测到它们我尝试输入如下：5 4 1 2 3 1 2 4 4 3 这是一个带有循环和分离节点的图，它输出“YES”但如果我以这种方式输入它输出“NO”： 5 4 1 2 1 3 2 4 3 4 所以一般来说，我需要检查图中的切口。

编辑：我改变了这个想法，它现在按预期工作：

#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;
}
于 2013-05-02T07:07:17.060 回答