题如其名。如何判断一幅图为树？

设x, y是一对父子节点。对每个x, y，都必须满足如下条件。

1.每个节点没有两个父亲。反例p[y] != y，即y已有父节点。

2.没有回路。反例find_set(x) == y，父节点的祖先是子节点。

以上在输入时即可判断。

3.没有森林。遍历p[i]，没有两个以上的祖先节点。

在这里，采用了并查集作为数据结构，可以用路径压缩，求得根节点。

#include <cstdio>
#include <string>

int p[1001], x, y, b[1001], ac, c[1001], k = 1;

int find_set(int i)
{
 if(p[i] != i)
 {
  p[i] = find_set(p[i]);
 }
 return p[i];
}

void proc()
{
 int i, t = 0;
 for(i = 0; i < 1001; i ++)
 {
  if(b[i])
  {
   c[find_set(i)] ++;
  }
 }

 for(i = 0; i < 1001; i ++)
 {
  if(c[i] > 1)
   t ++;
 }
 if(t > 1) ac = 0;
} 
  
void init()
{
 int i;
 for(i = 0; i <= 1000; i ++)
  p[i] = i;
 ac = 1;
 memset(b, 0, sizeof(b));
 memset(c, 0, sizeof(c));
}

void pt()
{
 printf("Case %d is ", k ++);
 if(ac)
  printf("a tree.\n");
 else
  printf("not a tree.\n");
}

int main()
{
 //freopen("in.txt", "r", stdin);
 init();
 while(scanf("%d %d", &x, &y))
 {
  if(x == -1)
   break;
  if(x == 0)
  {   
   proc();
   pt();
   init();
   continue;
  } 
  b[x] = 1, b[y] = 1;
  if(p[y] != y || find_set(x) == y) ac = 0;
  p[y] = find_set(x);     
 }
 return 0;
}
  
  

评论