PS:因为某人说这样能过只是因为这道题数据弱，所以我想求组数据（反例），谢谢路过的大牛们！

下面是我的代码（wa了N次参考了大牛的注意事项重写的，AC，G++，0ms）：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
/*
 空树 边数==0
 没有重边 -> 每个顶点只能有1个父亲
 没有环 -> 边数＝＝顶点数－1//边数<顶点数
 不能指向非父亲的祖先节点 -> 每个顶点只能有1个父亲
 不能是森林 -> 入度0==1
 */
#define M 110
int f[M];//i的父亲是f[i]，即f[i]->i
bool v[M];//访问标记
int vn, en;//顶点数，边数
int in[M];//入度
int mv;//顶点最大序号
bool flag;
void print(int n)
{
	printf("i\t");for (int i = 1; i <= n; ++ i) printf("%3d", i); printf("\n");
	printf("f[i]:\t");for (int i = 1; i <= n; ++ i) printf("%3d", f[i]); printf("\n");
	printf("in[i]:\t");for (int i = 1; i <= n; ++ i) printf("%3d", in[i]); printf("\n");
}
bool init() {
	int a, b;
	memset(f,0,sizeof(f));
	memset(v,0,sizeof(v));
	memset(in,0,sizeof(in));
	mv = vn = en = 0;
	flag = 1;
	while (1){
		//if (!flag) print(mv);///
		scanf("%d%d",&a,&b);
		if (a==-1&&b==-1) return 0;
		else if (a==0&&b==0) break;
		else if (!flag) continue;
		++ en;
		if (!v[a]) v[a] = 1, ++ vn;
		if (!v[b]) v[b] = 1, ++ vn;
		mv = max(mv, max(a,b));
		if (f[b] && f[b] != a) flag = 0;//有重边||指向非父亲的祖先节点
		++ in[b];
		f[b] = a;
	}
	return 1;
}
void solve() {
	int cnt = 0;
	if (!vn) flag = 1;
	else if (!flag || vn!=en+1) flag = 0;//顶点数－边数!=1
	else {
		for (int i = 1; i <= mv; ++ i)
			if (v[i] && !in[i]) ++ cnt;
		if (cnt != 1) flag = 0;
	}
}
int main()
{
	int cas = 0;
	while (init()) {
		solve();
		//print(mv);
		if (flag) printf("Case %d is a tree.\n", ++cas);
		else printf("Case %d is not a tree.\n", ++cas);
	}
	return 0;
}

• Re:为什么不可以使用“顶点数－边数＝＝1”来判断是否有环呢？谢谢路过的大牛们！ (21) infoG 2014-08-06 14:14:41