Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

给一个解法

Posted by zhengchuangscu at 2013-06-08 04:10:13 on Problem 1308
/*

原理:树的顶点数目 = 边数 + 1
顶点树,就是求一组数组中不重复元素的个数,可以用一个std::set
那样空的间会大一些,用到了一些系统库。
一下解法尽量不依赖库函数

*/


#include<stdio.h>
int main()
{
    unsigned char node_hash[50] = {0};
    int _byte_location, _byte_number, _node_cout, _max_node;
    _byte_number = _byte_location = _node_cout = _max_node = 0;
    int _pair1, _pair2, _case_num, _edge_count;
    _pair1 = _pair2  = _case_num = _edge_count = 0;
    while(scanf("%d %d", &_pair1, &_pair2) == 2 && _pair2 >= 0 && _pair1 >=0)
    {
        if(_pair1 == _pair2 && _pair1  == 0) 
        {
            _case_num++; 
            if(!_edge_count || _node_cout == 1 + _edge_count)// tree
                printf("Case %d is a tree.\n", _case_num);
            else
                printf("Case %d is not a tree.\n", _case_num);
            _edge_count = 0;
            _node_cout  = 0;
            for(int i=0; i < _max_node; i++)
                node_hash[i] = 0;
            //memset(node_hash, 0, _max_node);
            _max_node = 0;
            continue;
        }
        _edge_count++;
        _byte_number = _pair1 / 8;
        _byte_location = _pair1 % 8;
        if(!(node_hash[_byte_number] & 0x01 << (_byte_location)))
        {
            _node_cout++;
            node_hash[_byte_number] |= 0x01 << (_byte_location);
        }

        _byte_number = _pair2 / 8;
        _byte_location = _pair2 % 8;
        if(!(node_hash[_byte_number] & 0x01 << (_byte_location)))
        {
            _node_cout++;
            node_hash[_byte_number] |= 0x01 << (_byte_location );
        }
        if(_max_node < _pair1 > _pair2 ? _pair1 : _pair2)
            _max_node = _pair2 ? _pair1 : _pair2;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator