2012年9月26日 星期三

SPOJ Problem 1436: Is it a tree – PT07Y

C++ code colored by C++2HTML
#include <cstdlib>
#include <iostream>
#include <list>
#include <stdio.h>
#include <string.h>

using namespace std;

list<int> al[10001];
int ii, jj, node[10001];

long long int nn, magic_tri=2;
bool no;


void tt(int start_node, int pri_node)
{
    node[start_node] = magic_tri;
    if(false == no)
    {
        list<int>::iterator it;
        for(it=al[start_node].begin() ; it != al[start_node].end(); it++ )
        {
            if(*it == start_node)continue;
            if(*it == pri_node)continue;
            if(node[*it] == magic_tri)
            {
                no = true;
                break;
            }
            else 
            {
                jj = *it;
                tt(jj, start_node);
            }
        }
    }
}


int main()
{
    int ee, n1, n2;
    
    while(cin>>nn>>ee)
    {
        for(ii=0;ii<nn;++ii)
        {
            al[ii].clear();
        }
        for(ii=0;ii<10001;ii++)node[ii] = 0;
        for(ii=0;ii<ee;ii++)
        {
            cin>>n1>>n2;
            if(n1 == n2)continue;
            al[n1].push_front(n2);
            al[n2].push_front(n1);
        }
        if(0 == ee)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            no = false;
            tt(n1, 0);
            if(true == no)cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
    }
    //system("PAUSE");
    return 0;
}

沒有留言:

張貼留言

Wettlauf nach El Dorado 競逐黃金國 完全空想 山寨計劃: 咸陽之路

這幾天玩了競逐黃金國,以下簡稱黃金國。裡面有三種資源,水手,刀和錢。覺得可以山寨成另一個時空背景的遊戲:項羽和劉邦爭霸的時候,曾經有一刻,是劉邦跟項羽比,看誰先到咸陽,最後因為項羽在跟秦國主力軍戰鬥,所以是劉邦先到咸陽作終,這山寨遊戲的三種資源,可以換成水軍,陸軍和錢,水軍就如...