2049913 2006-08-31 22:34:46 Accepted 1268 C++ 00:00.00 448K St.Crux 题如其名。如何判断一幅图为树？ 设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;}      

评论