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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:注意~!~!~!需要注意的数据

Posted by Dorrow at 2016-05-03 02:24:09 on Problem 1308
In Reply To:注意~!~!~!需要注意的数据 Posted by:xuhanqiu at 2006-08-18 09:48:42
#include<iostream>
#include<cstring>
#include<cstdio>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf (1<<29)
using namespace std;
typedef long long ll;
const int N = 100000;
int f[N + 5];
bool vis[N + 5];
void init (int n)
{
    for (int i = 0; i <= n; ++i)
    {
        f[i] = i;
        vis[i] = 0;
    }
}
int getf (int x)
{
    int xx = x;
    while (x != f[x]) x = f[x];
    return f[xx] = f[x];
}
bool Merge (int x, int y)
{
    int fx = getf (x);
    int fy = getf (y);
    if (fx != fy)
    {
        f[fx] = fy;
        return 0;
    }
    return 1;
}
int main()
{
    int  kas = 0, x, y, mx = 0;
    bool fd = 0;
    init (N);
    while (~scanf ("%d %d", &x, &y) )
    {
        if (x <0|| y <0) break;
        if (x == 0 && y == 0)
        {
            if (fd)
            {
                printf ("Case %d is not a tree.\n", ++kas);
            }
            else
            {
                int only = 0;
                for (int i = 1; i <= mx; ++i)
                {
                    if (vis[i] && f[i] == i)
                    {
                        only++;
                        if (only > 1) break;
                    }
                }
                if (only > 1)
                {
                    printf ("Case %d is not a tree.\n", ++kas);
                }
                else
                {
                    printf ("Case %d is a tree.\n", ++kas);
                }
                init (N);
                fd = 0, mx = 0;
            }
        }
        else
        {
            mx = max (mx, max (x, y) );
            vis[x] = vis[y] = 1;
            if (fd) continue;
            if (Merge (x, y) ) fd = 1;
        }
    }
    return 0;
}


说的数据都过了 依旧WA=-=

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