并查集之 Is It A Tree?

Is It A Tree?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6600 Accepted Submission(s): 1545

Problem Description

A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.
There is exactly one node, called the root, to which no directed edges point.

Every node except the root has exactly one edge pointing to it.

There is a unique sequence of directed edges from the root to each node.

For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.

In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.

Input

The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.

Output

For each test case display the line ``Case k is a tree." or the line ``Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).

Sample Input

6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1

Sample Output

Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.

Source

North Central North America 1997

Recommend

Ignatius.L

这个题目真的恶心其他OJ我都AC了只有在杭电一直都是TLE 而hhw的代码其他OJ也全AC了但是在杭电确实WA 真的让人蛋疼啊学了三天的并查集了真的有点不想学了今天开始学二分匹配吧我们的代码在杭电上都没有AC 希望看到这篇文章的大牛能够帮我们解决这个问题

胡瀚武

 1 /**
 2     ---------------------------------------------------
 3         HuHanwu
 4         2012-7-12
 5         并查集快速判断每次输入是破坏树的性质
 6         时间复杂度: o(n) n为节点的个数
 7     ---------------------------------------------------
 8 */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 using namespace std;
13 #define MAXN 1000002
14 
15 int p[MAXN];    //存放父亲节点 只要存在父亲节点则此节点一存在某棵树中
16 int find(int x){ return p[x]==x ? x :(p[x]=find(p[x]));}    //查找父亲节点并 压缩路径
17 
18 int main()
19 {
20     int a,b,tree_num,t=0,father_a,father_b,TF; //tree_num 保存当前的树的棵数
21     while(~scanf("%d%d",&a,&b) && a!=-1)
22     {
23         tree_num=TF=1;
24         if(a==0)
25         {
26             printf("Case %d is a tree.\n",++t);
27             continue;
28         }
29         if(a==b)
30             TF=0;
31         else
32         {
33             memset(p,0,sizeof(p));  //用 0 初始化所有节点的父亲节点
34             p[a]=p[b]=a;
35         }
36         while(~scanf("%d%d",&a,&b) && a!=0)
37         {
38             if(TF==0 ) // 只要已经判断出该森林已经不是树
39                 continue;
40             if(p[b]!=0) // b节点已经存在
41             {
42                 father_b=find(b);
43                 if(b!=father_b) // b 节点不是树根就不可以连成一棵树
44                 {
45                     TF=0;
46                     continue;
47                 }
48                 else
49                 {
50                     if(p[a]!=0) // a b 节点都存在则树的的棵数-1
51                     {
52                         p[b]=find(a);
53                         tree_num--;
54                     }
55                     else        //a 节点不存在 而 b 节点存在
56                         p[b]=p[a]=a;
57                 }
58             }
59             else
60             {
61                 if(p[a]==0) // a b 节点都不存在则树的棵数+1
62                 {
63                     p[a]=p[b]=a;
64                     tree_num++;
65                 }
66                 else        //a 节点存在 而 b 节点不存在
67                     p[b]=find(a);
68             }
69         }
70         printf("Case %d ",++t);
71         if(TF==0)
72         {
73             printf("is not a tree.\n");
74             continue;
75         }
76         if(tree_num==1)      // 树的棵数是否为1
77             printf("is a tree.\n");
78         else
79             printf("is not a tree.\n");
80     }
81     return 0;
82 }

我的代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define  Max  100005
 6 
 7 int flag[Max],p[Max];
 8 
 9 int find(int x)
10 {
11     if(x!=p[x])
12     {
13         p[x]=find(p[x]);
14     }
15     return p[x];
16 }
17 
18 int uion(int a,int b)
19 {
20     a=find(a);
21     b=find(b);
22     if (a!=b)
23     {
24         p[a]=b;
25         return 1;
26     }    
27     else return 0;
28 }
29 
30 int main()
31 {
32     int n,i,m,q,a,b;
33     n=1;
34     bool t=true;
35     int f;
36     while (1)
37     {
38         memset(flag,0,sizeof(flag));
39         for (i=1;i<=Max;i++)
40         {
41             p[i]=i;
42         }
43         while (scanf("%d%d",&a,&b)!=EOF)
44         {    
45             if (a==-1||a==0)    break;    
46             flag[a]=flag[b]=1;
47             f=uion(a,b);
48             if (f==0)
49             {
50                 t=false;
51             }
52         }
53         if (a==-1) break;
54         if (a==0)
55         {
56         int fa;
57         for (i=1;i<=Max;i++)
58             if(flag[i])
59             {        
60                 fa=find(i);
61             }
62             for (i=1;i<=Max;i++)
63                 if(flag[i]&&fa!=find(i))
64                 {        
65                     t=false;
66                     break;
67                 }
68                 if (t)
69                     printf("Case %d is a tree.\n",n++);
70             else     printf("Case %d is not a tree.\n",n++);
71             t=true;
72         }
73     }
74     return 0;
75 }