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

個人合成作品