HDU 1325 Is It A Tree? (POJ 1308)

并查集问题。。。

这题以前做过……

以前做过……

做过……

过……

不过重做时候被吭得异常之爽……

在判断 vis[i]的时候。我记得标准C++是非0 即为真。

而我用C++ 提交的时候 if(vis[i]) 去直接给我WA了。

用G++ 就AC了。。。然后改成if(vis[i]==1) 交C++ 就AC了。

特瞄的我每次初始化都把 vis[i] 都赋值为 0 了。。都能出这种错?

求路过大神明示我的错误。

题意是判断是否是一棵树。

不能存在森林,用并查集合并,每个点的入度不能超过1.

比如 1 2 3 2 0 0 就不是一棵树。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[10010];
bool vis[10010];
int in[10010];
int father(int x)
{
    if(fa[x]!=x)
        fa[x]=father(fa[x]);
    return fa[x];
}
void intt()
{
    for(int i=0;i<=10010;i++)
        fa[i]=i,vis[i]=in[i]=0;
}
int main()
{
    intt();
    int x,y;
    bool flag=1;
    int tmp=0;
    int treecot=1;
    while(scanf("%d%d",&x,&y))
    {
        if(x<0&&y<0)return 0;
        tmp=max(tmp,max(x,y));
        if(x==0&&y==0)
        {
            int cot=0;
            for(int i=0;i<=tmp;i++)
            {
                if(vis[i]==1&&father(i)==i)cot++;//非常之坑爹!
                if(in[i]>1||cot>1)flag=0;
                if(!flag)break;
            }
            if(flag)printf("Case %d is a tree.\n",treecot++);
            else printf("Case %d is not a tree.\n",treecot++);
            intt();
            flag=1,tmp=0;
        }
        else
        {
            if(!flag)continue;
            int fx=father(x);
            int fy=father(y);
            if(fx==fy)flag=0;
            else
                {
                    fa[fy]=fx,in[y]++;
                    vis[x]=vis[y]=1;
                }
        }
    }
}

HDU 1325 Is It A Tree? (POJ 1308),布布扣,bubuko.com

时间: 07-03

HDU 1325 Is It A Tree? (POJ 1308)的相关文章

【HDU 4408】Minimum Spanning Tree(最小生成树计数)

Problem Description XXX is very interested in algorithm. After learning the Prim algorithm and Kruskal algorithm of minimum spanning tree, XXX finds that there might be multiple solutions. Given an undirected weighted graph with n (1<=n<=100) vertex

hdu 1325 Is It A Tree?(并查集)

题意:给出点.边,判断是不是一棵树 思路:问题是如何判断是不是树? 我总结了一下,但不官方,正确性待验证. 1.入度<=1(根节点为0,其他为1) 2.不能有环 3.只有一个根节点 #include<iostream> #include<stdio.h> #include<string.h> using namespace std; #define MAXN 50000 int fa[MAXN]; int a[MAXN]; int in[MAXN]; int se

HDU 4912 Paths on the tree(LCA+贪心)

题目链接 Paths on the tree 来源  2014 多校联合训练第5场 Problem B 题意就是给出m条树上的路径,让你求出可以同时选择的互不相交的路径最大数目. 我们先求出每一条路径(u, v)中u和v的LCA:w,按照路径的w的深度大小deep[w]对所有的路径排序. deep[w]越大,排在越前面. 然后从第一条路径开始一次处理,看c[u]和c[v]是否都没被标记过,如果都没被标记过则我们把这条路径选上,把答案加1. 同时标记以w为根的子树的节点为1,方便后续对c数组的查询

HDU 1535 Invitation Cards (POJ 1511)

两次SPFA.求 来 和 回 的最短路之和. 用Dijkstra+邻接矩阵确实好写+方便交换,但是这个有1000000个点,矩阵开不了. d1[]为 1~N 的最短路. 将所有边的 邻点 交换. d2[] 为 1~N 的最短路. 所有相加为 所要答案. 忧伤的是用SPFA  "HDU 1535"  AC了,但是POJ 一样的题 "POJ 1511" 就WA了. 然后强迫症犯了,不停的去测试. 题意中找到一句关键话 :Prices are positive integ

HDU 4925 Apple Tree(模拟题)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4925 解题报告:给你n*m的土地,现在对每一块土地有两种操作,最多只能在每块土地上进行两种操作,第一种是种苹果树操作,第二种是施肥操作,种苹果树操作可以使得该块地 长出一个苹果,施肥操作可以使得与这块土地相邻的土地的苹果产量变为原来的两倍,问可以得到的最多的苹果数量是多少? 例如一个4*4的土地,用1表示在该土地上做第一种操作,0表示在该土地上做第二种操作,可以得到最多苹果的操作如下: 0 1 0

hdu 4670 Cube number on a tree(点分治)

Cube number on a tree Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1628    Accepted Submission(s): 382 Problem Description The country Tom living in is famous for traveling. Every year, man

HDU 1325 Is It A Tree? 并查集

判断是否为树 森林不是树 空树也是树 成环不是树 数据: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 0 0 1 2 2 3 4 5 0 0 2 5 0 0 ans: no no yes #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype

POJ 2367:Genealogical tree(拓扑排序)

Genealogical tree Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2738 Accepted: 1838 Special Judge Description The system of Martians' blood relations is confusing enough. Actually, Martians bud when they want and where they want. They ga

HDU 2489 Minimal Ratio Tree(数据结构-最小生成树)

Minimal Ratio Tree Problem Description For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation. Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a