Is It A Tree?

#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;

#define MAXN 10001

class TreeJudge {
private:
    int f[MAXN]; //记录节点i的父节点或 -1*根节点r的树r的大小，确保树的无环性即最小连通性
    bitset<MAXN> graph; //是否在图内——用来数连通分量，确保树的连通性
    bitset<MAXN> son; //是否有爹——用来确保所有节点入度<=1 //由f[i]是否大于0可以判断
public:
    TreeJudge(){
        graph.reset(); son.reset(); memset(f, -1, sizeof(f));
    }
    int find(int x) {
        return f[x] < 0 ? x : f[x] = find(f[x]);
    }
    bool Union(int x, int y) {
        graph.set(x); graph.set(y);  // 图内所有节点（包括根节点）graph都置1

        int rx = find(x); int ry = find(y);
        if (son.test(y) || rx == ry)  return false; // y已经有爹了，要求入度至多1 || x与y属于同一棵树，要求无环 
        f[rx] += f[ry]; f[ry] = rx; son.set(y); 
        return true;
    }

    int countConnectedComponent() {//找出所有图中非子节点的节点个数,即graph1且son0
        return (graph ^ son).count();
    }
};

int main() {
    int x = 0, y = 0; int caseNumber = 1;
    while (true) {
        TreeJudge J; 
        bool isTree = true;
        while (cin >> x >> y && x > 0) // x 指向 y
            if (x == y || isTree && !J.Union(x, y)) isTree = false;
        if (x == -1 && y == -1) break;
        isTree &= (J.countConnectedComponent() <= 1);
        cout << "Case " << caseNumber++ << (isTree ? " is a tree." : " is not a tree.") << endl;
    }
    return 0;
}

并查集思路

 #include<stdio.h>
#include<string.h>
int Tree[10001];//存储各个节点的父节点 
int mark[10001];//节点是否是树中节点 

int findRoot(int node)
{
    if (Tree[node] == -1) return node;
    return findRoot(Tree[node]);
}

int main()
{
    int a, b, i;
    int flag = 1;
    int casecount = 1;
    memset(Tree, -1, 10001 * sizeof(int));
    while(scanf("%d%d", &a, &b) != EOF)
    {
        if (a == -1 && b == -1) break;
        if (a == 0 && b == 0)
        {
            int count = 0;
            int f = 0;
            for (i = 0; i < 10001; i++)
            {
                if (mark[i] == 1)f = 1;
                if (mark[i] == 1 && Tree[i] == -1) count++;
            }
            if (f == 0) printf("Case %d is a tree.\n", casecount);
            else if (count == 1 && flag == 1)printf("Case %d is a tree.\n", casecount);
            else printf("Case %d is not a tree.\n", casecount);
            casecount++;
            flag = 1;
            // 初始化 
            for (i = 0; i < 10001; i++)
            {
                mark[i] = 0;
                Tree[i] = -1;
            }
        }
        else 
        {
            mark[a] = 1;
            mark[b] = 1;
            if (Tree[b] != -1 && Tree[b] != a)
            {
                flag = 0;
                continue;
            }
            int rootA = findRoot(a);
            int rootB = findRoot(b);
            if (rootA == rootB) flag = 0;//有环 
            else Tree[b] = a;
        }
    }
    return 0; 
}

#include <cstdio>
using namespace std;

bool vis[10000];
int in[10000];
int tree[10000];

int findRoot(int x) {
    if(tree[x] == -1) return x;
    int ret = findRoot(tree[x]);
    tree[x] = ret;
    return ret;
}

int main() {
    int cas = 1;
    int a, b;
    while(scanf("%d%d", &a, &b) == 2) {
        if(a < 0 && b < 0) break;
        if(a==0 && b==0){
            printf("Case %d is a tree.\n",cas++);
            continue;
        }
        for(int i = 1; i <= 10000; i++) {
            vis[i] = false;
            in[i] = 0;
            tree[i] = -1;
        }
        vis[a] = true;
        vis[b] = true;
        in[b]++;
        a = findRoot(a);
        b = findRoot(b);
        if(a != b) tree[a] = b;
        while(scanf("%d%d", &a, &b) == 2) {
            if(a == 0 &&b == 0) break;
            vis[a] = true;
            vis[b] = true;
            in[b]++;
            a = findRoot(a);
            b = findRoot(b);
            if(a != b) tree[a] = b;
        }
        bool res = true;
        int root = 0;
        int component = 0;
        for(int i = 1; i <= 10000; i++) {
            if(vis[i] && in[i] == 0) root++;
            if(in[i] >= 2) res = false;
            if(vis[i] && tree[i] == -1) component++;
        }
        if(root != 1) res = false;
        if(component != 1) res = false;
        if(res == true) printf("Case %d is a tree.\n", cas++);
        else printf("Case %d is not a tree.\n", cas++);
    }

    return 0;
}

	

//并查集思想，需要判断 一、连通分量是否为1(一棵树) 二、是否只有一个根节点(入度为0) 三、除根节点外每个结点入度应该都为1 四、空树也算树

#include <bits/stdc++.h>
using namespace std;
         
const int MAXN = 10001;
int father[MAXN];                      //每个结点的父亲节点，为了后面递归查找每个结点的根节点
int height[MAXN];                      //每个结点的高度
int inDegree[MAXN];                    //存放每个结点的入度
bool vis[MAXN];                        //每个结点是否在某次建树的过程中用到了，用到了设为true，没用到设为false，方便最后判断

void Init(){
    for(int i = 0; i < MAXN; ++i){
        father[i] = i;                  //初始化，最开始每个结点都是单个的集合，让他的父亲等于他自己，为后面的Find()做准备
        height[i] = 0;                  //只有一个结点的高度设为0
        inDegree[i] = 0;                //入度初始化为0
        vis[i] = false;                 //false表示没被访问
    }
    return;
}

int Find(int x){                        //寻找每个结点的根结点
    if(x != father[x]){
        father[x] = Find(father[x]);    //压缩路径
    }
    return father[x];
}

void Union(int x, int y){              //并查集合并操作，方便最后查询连通分量
    x = Find(x);
    y = Find(y);
    if(x != y){
        if(height[x] < height[y]){
            father[x] = y;
        }
        else if(height[y]  < height[x]){
            father[y] = x;
        }
        else{
            father[y] = x;
            height[x]++;
        }
    }
    return;
}

bool IsTree(){                                //判断是否满足题意
    bool flag = true;
    int component = 0;
    int root = 0;
    for(int i = 0; i < MAXN; ++i){ 
        if(!vis[i]){                         //某个点为假，证明这个顶点就不在这棵树里，不用进行下面的操作了
            continue;
        }
        if(father[i] == i){
            component++;                     //计算连通分量，连通图的连通分量应该为1
        }
        if(inDegree[i] == 0){                //入度为0的点应该只有1个，就是最终那棵树的根结点
            root++;
        }
        else if(inDegree[i] > 1){            //如果入度大于1，说明这个点被两条边指了，不满足树的定义
            flag = false;
        }
    }
    if(component != 1 || root != 1){         //由上面讲的知道，不满足要求，就不是树
        flag = false;
    }
    if(component == 0 && root == 0){         //空树也是树
        flag = true;
    }
    return flag;
}

int main(){
    int x, y;
    int num = 0;
    Init();
    while(cin >> x >> y){
        if(x == -1 && y == -1){
            break;
        }
        if(!(x == 0 && y == 0)){
            Union(x, y);
            inDegree[y]++;                //由x指向y，则y的入度+1
            vis[x] = true;                //这个顶点在树(集合)中，设为true
            vis[y] = true;
        }
        else{
            if(IsTree()){
                cout << "Case " << ++num << " is a tree." << endl;
            }
            else{
                cout << "Case " << ++num << " is not a tree." << endl;
            }
            Init();
        }
    }
    return 0;
}

/* 基本思想：
 *  1. e + 1 = v; 注意v可能为零也算树。并且如果有环这个条件也可以把环排除
 *  2. 入度为零的顶点个数为1.(只有一个root，也可以用并查集)
 */

#include <stdio.h>
#include <set>
#include <map>

using namespace std;

int main()
{
    int a, b, cas = 1, cnt = 0, edge = 0;
    map<int, int> inDegree;
    set<int> V;

    while (scanf("%d%d", &a, &b) != EOF) {
        if (a < 0 && b < 0) {
            break;
        } else if (a == 0 && b == 0) {
            if (V.size() && edge + 1 != V.size()) {
                printf("Case %d is not a tree.\n", cas);
                goto clear;
            }

            cnt = 0;
            for (auto i : V) {
                if (inDegree[i] == 0) {
                    if (++cnt > 1) {
                        printf("Case %d is not a tree.\n", cas);
                        goto clear;
                    }
                }
            }

            printf("Case %d is a tree.\n", cas);
clear:
            inDegree.clear();
            V.clear();
            edge = 0;
            cas++;
        } else {
            V.insert(a); V.insert(b);
            inDegree[b]++;
            ++edge;
        }
    }

    return 0;
}

特判：

没有边也算树

0 0 is tree

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
// 1). 没有度大于1的节点
// 2). 有且只有一个度为0的节点 判断环
// 3). 空
int main(){
    int p1,p2;
    int cnt=1;
    while(cin>>p1>>p2&&!(p1==-1&&p2==-1)){
        vector<pair<int,int> > li;
        while(p1!=0&&p2!=0){
            li.push_back(make_pair(p1,p2));
            cin>>p1>>p2;
        }

        int fa[10005];
        int contained[10005];
        int flag=0;
        fill(fa,fa+10005,0);
        fill(contained,contained+10005,0);
        for(int i=0;i<li.size();i++){
            if(fa[li[i].second]>0){
                flag=1;
                break;
            }
            else {
                fa[li[i].second]++;
                contained[li[i].first]=1;
                contained[li[i].second]=1;
            }
        }
        // circle
        if(flag==0){
            int zerocnt=0;
            for(int i=1;i<10005;i++){
                if(contained[i]==1&&fa[i]==0) zerocnt++;
            }
            if(zerocnt!=1) flag=1;
        }
        // empty
        if(li.empty()) flag=0;
        if(flag==1) cout<<"Case "<<cnt++<<" is not a tree."<<endl;
        else cout<<"Case "<<cnt++<<" is a tree."<<endl;

        li.clear();
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;

const int maxn = 10001;

map<int, int> couple;

int main()
{
    
    int m, n;
    int mycase = 0;         // 统计 case 数量
    int count = 0;          // 用于统计本树节点个数
    while(cin >> m >> n)
    {
        // 结束标志
        if(m == -1 && n == -1)
        {
            break;
        }

        if(m == 0 && n == 0)
        {
            if(count == 0)
            {
                // 空树
                cout << "Case " << ++mycase << " is a tree." << endl;
                continue;
            }

            // 遍历查找是否只有一个节点入度为0，其余节点入度为 1
            int flag0 = 0;      // 标志节点入度为 0 的节点个数
            int flag2 = 0;      // 标志是否有节点入度 大于 1
            for(map<int, int>::iterator it=couple.begin(); it != couple.end(); ++it)
            {
                if(it->second == 0)
                {
                    ++flag0;
                }
                if(it->second > 1)
                {
                    ++flag2;
                }
            }

            // 输出
            if(flag0 == 1 && flag2 == 0)
            {
                cout << "Case " << ++mycase << " is a tree." << endl;
            }
            else
            {
                cout << "Case " << ++mycase << " is not a tree." << endl;
            }

            // map 及 计数器 初始化 
            couple.clear();
            count = 0;
        }
        else
        {
            ++count;
            // 入度
            if(couple.count(n))
            {
                couple[n] += 1;
            }
            else
            {
                couple[n] = 1;
            }
            // 初度
            if(!couple.count(m))
            {
                couple[m] = 0;
            }
        }

    }

    return 0;
}

//看了以上的各个答案，大多用出度入度解决，可是这样并不能处理有环的情况，
//比如 1 2 3 4 4 5 5 3 0 0 ，这不是一棵树，但是用出度会判断为一棵树。
//但是这样确实可以通过所有测试，难道是我庸人自扰了
//以下借用并查集的思路实现
#include<iostream>
using namespace std;
#include<vector>
#include<map>
int find(map<int, int> &m, int x) {
	int r = x;
	while (m.find(r) != m.end() && m[r] != x)
		r = m[r];
	return r;
}
bool isTree(map<int, int> &m) {
	int r = find(m, m.begin()->first);
	for (map<int, int>::iterator it = m.begin();it != m.end();it++) {
		if (find(m, it->first) != r || find(m, it->first) == -1)
			return false;
	}
	return true;
}
int main() {
	int a, b, times = 0;
	map<int, int> m;
	while (cin >> a >> b) {
		if (a == -1 && b == -1)return 0;
		if (a == 0 && b == 0) {
			cout << "Case " << ++times << " is " << (isTree(m) ? "" : "not ") << "a tree." << endl;
			m.clear();
		}
		else {
			if (m.find(b) != m.end() || a==b)
				m[b] = -1;
			else
				m[b] = a;
		}
	}
}

#include <bits/stdc++.h>
using namespace std;
int main(){
	unordered_map<int,int> m;
	for(int k=0,s,e,f=0;cin>>s>>e && s>-1 && e>-1;){
		if (s==0 && e==0){
			for(auto se:m){
				if (se.second==0) f++;
				if (se.second>1 || f>1) {
					f=0;
					break;
				}
			}
			cout<<"Case "<<++k<<" is "<<(f||m.size()==0?"":"not ")<<"a tree."<<endl;
			f=0;
			m.clear();
			continue;
		}
		if(m.find(s)==m.end()) m[s]=0;
		m[e]++;
	}
	return 0;
} 

#include <cstdio>
#include <iostream>

using namespace std;

/*
	1、只有一个根节点——入度为0的结点
	2、并查集只有一个连通分量 
*/ 

const int MAXN = 10000;

int father[MAXN];// 父亲结点 
int height[MAXN];// 高度 
int inDegree[MAXN];// 该结点的度 
bool visit[MAXN];//	标记——是否存在该结点 

// 初始化 
void Init() {
	for (int i = 0; i < MAXN; i++) {
		father[i] = i;
		height[i] = 0;
		inDegree[i] = 0;
		visit[i] = false;
	}
	return ;
} 

// 查找父亲
int Find(int x) {
	if (x != father[x]) {
		// 将该结点的所有father都修改为根 
		father[x] = Find(father[x]); // 即变得只有两层 
	}
	// x 就是子树的根 
	return father[x];
} 

// 合并集合
void Union(int x, int y) {
	x = Find(x);// 记住要求其父结点！！！！！ 
	y = Find(y);
	if (x != y) {
		if (height[x] < height[y]) {
			father[x] = y;
		}else if (height[x] > height[y]) {
			father[y] = x;
		}else {
			father[y] = x;
			height[x]++;
		}
	}
	return ;
} 

// 判断是否为一棵树
bool isTree() {
	bool flag = true;// 判断是否为树的标志 
	int component = 0;//	连通分量个数 
	int root = 0;//		根结点数目 
	for (int i = 0; i < MAXN; i++) {
		if (!visit[i]) {// 若不存在该结点 
			continue;
		}
		if (father[i] == i) {// 存在一个连通分量，因为只有自己和自己相等才是一个分支 
			component++;
		}
		if (inDegree[i] == 0) {// 入度为0的结点是root 
			root++;
		}else if (inDegree[i] > 1) {// 入度不满足要求，入度只可能是 0/1 
			flag = false;
		} 
	}
	// 含有多个连通分量 || 多个根 
	if (component != 1 || root != 1) {// 不符合树定义 
		flag = false;
	}
	// 没有连通分量 || 无根 
	if (component == 0 && root == 0) {// 空集也是树 
		flag = true;
	}
	return flag;
}

// 判断是否为一棵树 
int main() {
	int x, y;
	int casenum = 0;
	Init();
	while (scanf("%d %d", &x, &y) != EOF) {
		if (x == -1 && y == -1) {// 全部输入完毕 -1 -1 
			break;
		}
		if (x == 0 && y == 0) {// 结束标志 0 0 
			if (isTree()) {// 满足树的条件 
				printf("Case %d is a tree.\n", ++casenum);
			}else {
				printf("Case %d is not a tree.\n", ++casenum);
			}
			Init();// 重新初始化 
		}else {
			Union(x, y);
			inDegree[y]++;// 入度++ 
			// 设置为访问过 
			visit[x] = true;
			visit[y] = true;
		}
	}
	return 0;
}
//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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int n = 10001;
    public static int[] father = new int[n];//存储每个节点的父节点
    public static boolean[] isNode = new boolean[n]; //记录对应位置是否有节点
    public static int[] inDegree = new int[n];

    public static void init(){
        //对每个节点进行初始化，最开始每个节点都是一个单独的树
        for (int i = 0; i < n; i++) {
            father[i] = -1; //初始时刻每个节点的父节点都标记为-1
            isNode[i] = false;
            inDegree[i] = 0;
        }
    }

    public static boolean isTree(){
        //通过判断在这个图中，除了根节点，每个节点是否只有一个入度，对于根节点，是否只有一个节点入度为0
        int numRoot = 0; //记录根节点的个数：入度为0
        int node = 0; //记录节点个数
        for (int i = 0; i < n; i++) {
            if(!isNode[i]) continue; //此处没有节点，则继续下一次循环
            node++;
            if(inDegree[i] > 1){
                //有节点入度大于1，说明不是树
                return false;
            }
            if(inDegree[i] == 0){
                //是根节点
                numRoot++;
            }
        }

        //空树也是树
        if(node == 0) return true;
        else { //不是空树
            //如果树中的根节点个数大于1，肯定不是树
            if(numRoot > 1) return false;
            //接下来的情况只有根节点的个数为0或1
            //如果树中没有根节点，则不是树
            return numRoot != 0;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = 1;
        init();
        while(sc.hasNextInt()){
            int start = sc.nextInt();
            int end = sc.nextInt();
            if(start < 0 && end < 0) break;
            if(start == 0 && end == 0 && isTree()){
                System.out.printf("Case %d is a tree.\n", i);
                i++;
                init(); //判断完一个图，继续判断下一个图
            }else if(start == 0 && end == 0){
                System.out.printf("Case %d is not a tree.\n", i);
                i++;
                init();
            }else {
                father[end] = start;
                isNode[start] = true;
                isNode[end] = true;
                inDegree[end]++;
            }
        }
    }
}