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;
}

しかし、それは間違った答えを生成するだけで、その理由はわかりません（このオンライン裁判官の問題でテストしました 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 に答える