撰写
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.
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.
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.
题意：就是判一棵有向树，从一个根节点能到达任意一个结点
题解：mmp这题有bug，数据太弱，根本不判断是否有点入度大于2导致非树，反正是加了个自己到自己的边让我wa了n次mmp，另外，在并查集操作时，并没有所谓的顺序一说，因为对于这个树的图，在满足了无环的条件下（find(a)!=find(b)），只要这个图不是森林，那么只会有一个根节点，无论这个根结点实际上是不是真正的根节点，当然，如果需要知道真正的根节点，请顺序输入。
代码1：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e5+5;
vector<int>G[maxn];
set<int>s;
bool vis[maxn];
int mark[maxn];
int dfs(int u){
vis[u]=true;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v])dfs(v);
}
}
int main(){
int u,v,cnt=0;int sign;
CLR(vis);
int c = 0;
while(1){
scanf("%d%d",&u,&v);
if(u+v==-2) break;
if(u+v==0) { printf("Case %d is a tree.\n",++c); continue; }
cnt++;
s.insert(u); s.insert(v);
mark[v]++;
G[u].push_back(v);
G[v].push_back(u);
sign = u;
while(scanf("%d%d", &u,&v)){
if(u==0&&v==0){
int flag=1;
if(cnt!=s.size()-1)flag = 0;
else{
int aha = 0;
dfs(sign);
rep(i,1,maxn){
if(vis[i]){
aha++;
if(mark[i]>1){
flag = 0;
break;
}
}
}
if(aha!=s.size())flag=0;
}
if(flag)printf("Case %d is a tree.\n",++c);
else printf("Case %d is not a tree.\n",++c);
rep(i,1,maxn)G[i].clear();
s.clear();
cnt=0;
CLR(vis);
CLR(mark);
break;
}
mark[v]++;
cnt++;
sign=u;
s.insert(u);
s.insert(v);
G[u].push_back(v);
G[v].push_back(u);
}
}
}
代码2：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e5+5;
bool vis[maxn];
int pre[maxn];
int rankk[maxn];
int rank[maxn];
void init(){
rep(i,1,maxn){
vis[i]=false;
pre[i]=i;
rankk[i]=1;
rank[i]=0;
}
}
int find(int x){
return x==pre[x]?x:pre[x]=find(pre[x]);
}
void unionn(int x,int y){
x = find(x);
y = find(y);
if(x==y)return;
else if(rankk[x]>rankk[y]) pre[y]=x;
else{
pre[x] = y;
if(rankk[x]==rankk[y])rankk[y]++;
}
}
int main()
{
int x,y;
int cur = 0;
while(1){
init();
scanf("%d%d",&x,&y);
if(x+y==-2) break;
if(x+y==0) { printf("Case %d is a tree.\n", ++cur); continue; } //这是此题易悲剧的地方；
int flag=1;
vis[x]=true;vis[y]=true;
rank[y]++;
if(find(x)!=find(y))unionn(x,y);//还有这里，丧心病狂，第一步就输入两个一样的数？？？
else flag = 0;
while(scanf("%d%d", &x,&y)==2){
if(x==0&&y==0){
break;
}
rank[y]++;
if(vis[x]&&vis[y]){
if(find(x)==find(y))flag=0;
else unionn(x,y);
}else{
vis[x]=true;
vis[y]=true;
unionn(x,y);
}
}
if(!flag)printf("Case %d is not a tree.\n", ++cur);
else{
int cnt = 0;
rep(i,1,1e5){
if(vis[i]){
if(pre[i]==i){
cnt++;
if(rank[i]>=2)cnt=100;//任意大于1的数即可
}
}
}
if(cnt==1)printf("Case %d is a tree.\n", ++cur);
else printf("Case %d is not a tree.\n", ++cur);
}
}
return 0;
}