題目連結: https://zerojudge.tw/ShowProblem?problemid=c131
# 內容
在資料結構中，樹（tree）的定義為空的（null, void, nothing），或是由一或多個節點以及有向邊所組成，且需滿足以下的條件：
- 只有一個點，我們稱做根（root），沒有任何邊指向他。
- 除了根以外的節點，都只有一個邊指向他。。
- 從根到任一節點，都只有唯一的路徑。
寫一個程式，讀入一圖形的資料，然後回答該圖是否為樹。
# 解題思路
就依照題目的意思去做判定吧
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
int tree[105]; // 紀錄父節點 | |
set<int> record; | |
set<int>::iterator it; | |
// 是否有迴圈 | |
bool cycle(int n,int root){ | |
if(n==root) return false; | |
int now = tree[n]; | |
while(true){ | |
if(now==root) return false; // 真的是根ㄟ | |
if(now==n) return true; // 迴圈構成啦 | |
now = tree[now]; // 往上追溯 | |
} | |
} | |
int main() { | |
for(int a,b,cnt=1;scanf("%d %d",&a,&b)!=EOF&&a>=0&&b>=0;cnt++,record.clear()) { | |
if(a==0&&b==0) {printf("Case %d is a tree.\n",cnt); continue;} | |
int root=-1; | |
bool is_a_tree=true; | |
memset(tree,-1,sizeof(tree)); | |
tree[b]=a; | |
record.insert(a),record.insert(b); | |
for(;scanf("%d %d",&a,&b)!=EOF&&(a||b);) { | |
if(tree[b]==-1) tree[b]=a; | |
else is_a_tree=false; | |
record.insert(a),record.insert(b); | |
} | |
for(it=record.begin();it!=record.end();it++) | |
if(tree[*it]==-1) | |
if(root==-1) root=*it; | |
else is_a_tree=false;// 根只有一個 | |
for(it=record.begin();it!=record.end()&&is_a_tree;it++) | |
if(cycle(*it,root)) is_a_tree=false; | |
if(is_a_tree) printf("Case %d is a tree.\n",cnt); | |
else printf("Case %d is not a tree.\n",cnt); | |
} | |
return 0; | |
} |
