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 and less than 10000.
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).
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
Case 1 is a tree. Case 2 is a tree. Case 3 is not 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; }
#include<bits/stdc++.h> using namespace std; const int maxn=10000; int parent[maxn]; int height[maxn]; int indegree[maxn]; int vis[maxn]; void Initial(){ for(int i=0;i<maxn;i++){ parent[i]=i; height[i]=0; indegree[i]=0; vis[i]=false; } return; } int Find(int x){ if(x!=parent[x]){ parent[x]=Find(parent[x]); } return parent[x]; } void Union(int x,int y){ x=Find(x); y=Find(y); if(x!=y){ if(height[x]<height[y]){ parent[x]=y; }else if(height[x]>height[y]){ parent[y]=x; }else{ parent[y]=x; height[x]++; } } return; } bool IsTree(){ int root=0;//入度为0个数看indegree int componet=0;//连通分量个数看parent bool flag=true; for(int i=0;i<maxn;i++){ if(!vis[i]){ continue; } if(i==parent[i]){ componet++; } if(indegree[i]==0){ root++; }else if(indegree[i]>1){ flag= false; } if(componet!=1||root!=1){ flag= false; } if(componet==0&&root==0){ flag=true; } } return flag; } int main(){ int n,m; int num=1; Initial(); while(cin>>n>>m){ if(n==-1&&m==-1)break; if(n==0&&m==0){ if(IsTree()){ cout<<"Case "<<num<<" is a tree."<<endl; num++; }else{ cout<<"Case "<<num<<" is not a tree."<<endl; num++; } Initial(); }else{ Union(n,m); indegree[m]++; vis[n]=true; vis[m]=true; } } 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; }
#include<bits/stdc++.h> using namespace std; unordered_set<int> s; int cnt, vis[10000], inD[10000]; vector<vector<int>> adj; void dfs(int u) { vis[u] = 1; cnt++; //遍历到的顶点数 int v; for (int i = 0; i < adj[u].size(); i++) { v = adj[u][i]; if (vis[v] == 0) dfs(v); } } int main() { int a, b, i = 1; while (cin >> a >> b) { if (a == -1 && b == -1) break; printf("Case %d is", i++); if (a == 0 && b == 0) { //空树 printf(" a tree.\n"); continue; } int num = 0, root, inD_0_num=0; //inD_0_num表示入度为0的结点数 cnt = 0; memset(vis, 0, sizeof(vis)); memset(inD, 0, sizeof(inD)); s.clear(); adj.clear(); adj.resize(10000); do { //do...while结构更适合 if (a == 0) break; num++; //边数 adj[a].push_back(b); inD[b]++; s.insert(a); s.insert(b); //存顶点数 } while (cin >> a >> b); for (int k : s) { //判断入度为0的顶点数 if (inD[k] == 0) { inD_0_num++; if (inD_0_num > 1) break; root = k; } } if (num == s.size() - 1&&inD_0_num == 1) { //边数为顶点数-1,且入度为0的结点只有一个 dfs(root); printf("%s", cnt == s.size() ? " " : " not "); } else printf(" not "); printf("a tree.\n"); } return 0; }
#include<iostream> using namespace std; const int maxn=10000; int father[maxn]; int inDegree[maxn]; //节点入度 bool vis[maxn]; //是否是出现过的节点 int n=0; void init(){ //初始化 for(int i=0;i<maxn;i++){ father[i]=i; inDegree[i]=0; vis[i]=false; } } int findFather(int x){ //寻找父节点 int a=x; while(x!=father[x]){ x=father[x]; } while(a!=father[a]){ //合并路径 int z=a; a=father[a]; father[z]=x; } return x; } void Union(int a,int b){ int faA=findFather(a); int faB=findFather(b); if(faA!=faB) father[faA]=faB; } bool isTree(){ int component=0; //连通分量个数 int root=0; //根节点个数 bool flag=true; for(int i=0;i<=n;i++){ if(vis[i]==false){ continue; } if(father[i]==i){ component++; } if(inDegree[i]==0){ root++; }else if(inDegree[i]>1){ flag=false; } } if(component!=1||root!=1) flag=false; if(component==0&&root==0) flag=true; return flag; } int main(){ int a,b; int current=0; init(); while(scanf("%d %d",&a,&b)!=EOF){ if(a==-1&&b==-1) break; else if(a==0&&b==0){ if(isTree()){ printf("Case %d is a tree.\n",++current); }else{ printf("Case %d is not a tree.\n",++current); } init(); }else{ Union(a,b); inDegree[b]++; vis[a]=true; vis[b]=true; n=max(n,a); n=max(n,b); } } }
#include <iostream> using namespace std; const int maxd=10000; int Father1[maxd]; bool is=false; int find(int x){ if(x!=Father1[x]) Father1[x] = find(Father1[x]); return Father1[x]; } void Uniond(int x,int y){ int a=find(x); int b=find(y); if(b!=y||a==b){ is=true; return; } Father1[y]=a; } int main(){ is=false; for(int i=1;i<maxd;i++) Father1[i]=0; int n,m,cased=0; while(scanf("%d %d",&n,&m)){ if(n==-1&&m==-1) break; if(n==0&&m==0){ cased++; if(is){ printf("Case %d is not a tree.\n",cased); is=false; for(int i=1;i<maxd;i++) Father1[i]=0; continue; } int count=0; for(int i=1;i<maxd;i++){ if(i==Father1[i]){ count++; if(count>1){ is=true; break; } } } if(is) printf("Case %d is not a tree.\n",cased); else printf("Case %d is a tree.\n",cased); is=false; for(int i=1;i<maxd;i++) Father1[i]=0; } if(Father1[n]==0) Father1[n]=n; if(Father1[m]==0) Father1[m]=m; Uniond(n,m); } 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<iostream> #include<map> #include<cstdio> using namespace std; map<int, int> inDegree; bool isTree() { if (inDegree.empty()) return true; //空树也算树 int rootCount = 0; for (auto iter = inDegree.begin(); iter != inDegree.end(); iter++) { if (iter->second == 0) rootCount++; //入度为0则计入根节点数 if (iter->second > 1 || rootCount > 1) {//若入度大于1或根节点数大于1,显然非树 return false; } } return rootCount; //循环结束后,若根节点数非0,则返回true } int main() { int a, b; int caseNumber = 0; bool wrong = false; //利用wrong布尔变量判断是否为树 while(scanf("%d%d", &a, &b) != EOF){ if (a == -1) break; if (!a && !b) { //遇 0 0 输入,则判断是否为树,判断结束后重置变量 if (!isTree()) wrong = true; if (!wrong) printf("Case %d is a tree.\n", ++caseNumber); else printf("Case %d is not a tree.\n", ++caseNumber); wrong = false; //变量、映射重置 inDegree.clear(); continue; } if (a == b) wrong = true; //排除自环,注意0 0的情况会在上一个if语句中判断 inDegree[a]; //比较随便的一种写法,这样写后,若inDegree[a]不存在,则会在映射中创造一个,并赋值为0 inDegree[b]++; //入度增加 } return 0; }
#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]++; } } } }