c131 - 00615 - Is It A Tree?
題目描述
題目要求判斷給定的有向圖是否為一棵樹。一棵樹的定義是：只有一個根節點沒有入度，除了根節點外，其他節點都有唯一一個入度，並且從根節點到任何其他節點都只有唯一路徑。
解題思路
程式碼使用鄰接矩陣 tree 來表示圖，all 陣列記錄節點是否存在。程式首先讀取邊，建立鄰接矩陣。然後，程式檢查以下條件：
- 節點數量等於邊數量加一。
- 不存在雙向邊。
- 只有一個根節點（入度為0）。
- 除了根節點外，每個節點的入度為1。
- 從根節點出發，可以到達所有其他節點，並且不存在環。
ff 函數使用深度優先搜尋 (DFS) 來檢測環。如果從一個節點出發，再次回到該節點，則存在環。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是節點的最大數量。這是因為鄰接矩陣的遍歷和 DFS 函數都需要 O(N^2) 的時間。
- 空間複雜度: O(N^2)，主要用於儲存鄰接矩陣
tree。
程式碼
#include <iostream>
using namespace std;
int tree[105][105],all[105],x,y,chat=1,ca;
void ff(int now,int begin,int step){
if(now==begin&&step){
chat=0;
return;
}
else
for(int i=0;i<101;++i)
if(tree[i][now])
ff(i,begin,step+1);
}
int main(){
while(cin >> x >> y){
if(x==-1)break;
else if(x==0&&y==0){
int node=0,line=0,root=0;
for(int i=0;i<101;++i){
node+=all[i];
for(int j=0;j<101;++j){
line+=tree[i][j];
if(tree[i][j]&&tree[j][i])
chat=0;
}
}
if(node!=line+1)
chat=0;
if(node==0&&line==0)
chat=1;
for(int i=0;i<101&&chat;++i){
if(all[i]){
int fa=0;
for(int j=0;j<101;++j)
fa+=tree[j][i];
if((fa==0&&root)||fa>1)
chat=0;
else if(fa==0)
root=i;
}
}
for(int i=0;i<101&&chat;++i)
if(all[i]&&i!=root)
ff(i,i,0);
if(chat)
cout << "Case " << ++ca << " is a tree.\n";
else
cout << "Case " << ++ca << " is not a tree.\n";
for(int i=0;i<101;++i){
all[i]=0;
for(int j=0;j<101;++j)
tree[i][j]=0;
}
chat=1;
}
else{
++tree[x][y];//x is y's father
all[x]=1;
all[y]=1;
}
}
}