b674 - Is It A Tree
題目描述
題目要求判斷給定的有向圖是否為一棵樹。一棵樹需要滿足以下條件：
- 恰好有一個根節點，沒有指向它的邊。
- 除了根節點外，每個節點恰好有一條指向它的邊。
- 從根節點到每個節點存在唯一路徑。
解題思路
程式碼使用鄰接矩陣 tree 來表示圖。首先，程式讀取邊的數量 n，並建立鄰接矩陣。然後，程式計算節點的數量 node 和邊的數量 line。如果 node 不等於 line + 1，則圖不是樹。接著，程式檢查是否存在雙向邊，如果存在，則圖不是樹。程式還檢查是否存在多個根節點或一個節點有多個父節點，如果存在，則圖不是樹。最後，程式使用深度優先搜尋 (DFS) ff 函數來檢查圖中是否存在循環。如果沒有循環，則圖是樹，輸出 "y"，否則輸出 "n"。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是節點的最大數量。這是因為鄰接矩陣的遍歷和 DFS 函數都需要 O(N^2) 的時間。
- 空間複雜度: O(N^2)，主要用於儲存鄰接矩陣
tree。
程式碼
#include <iostream>
using namespace std;
int tree[1005][1005],all[1005],x,y,chat=1,ca,n;
void ff(int now,int begin,int step){
if(now==begin&&step){
chat=0;
return;
}
else
for(int i=0;i<1001;++i)
if(tree[i][now])
ff(i,begin,step+1);
}
int main(){
while(cin >> n){
if(!n)break;
else{
while(n--){
cin >> x >> y;
++tree[x][y];//x is y's father
all[x]=1;
all[y]=1;
}
int node=0,line=0,root=0;
for(int i=0;i<1001;++i){
node+=all[i];
for(int j=0;j<1001;++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<1001&&chat;++i){
if(all[i]){
int fa=0;
for(int j=0;j<1001;++j)
fa+=tree[j][i];
if((fa==0&&root)||fa>1)
chat=0;
else if(fa==0)
root=i;
}
}
for(int i=0;i<1001&&chat;++i)
if(all[i]&&i!=root)
ff(i,i,0);
if(chat)
cout << "y\n";
else
cout << "n\n";
for(int i=0;i<1001;++i){
all[i]=0;
for(int j=0;j<1001;++j)
tree[i][j]=0;
}
chat=1;
}
}
}