b517 - 是否為樹-商競103
題目描述
題目給定一個圖形的邊的資訊，要求判斷該圖形是否為一棵樹。輸入包含多組測試案例，每組案例包含 n 條邊，邊的表示形式為 i,j，其中 i 和 j 是相鄰節點的編號。
解題思路
判斷一個圖形是否為樹，需要滿足兩個條件：
- 圖是連通的。
- 圖中沒有環。
程式碼首先讀取邊的資訊，並建立鄰接矩陣 a。然後，檢查圖的連通性。如果圖的節點數量不等於邊的數量加一，則圖不是樹。如果節點數量等於邊的數量加一，則使用深度優先搜尋 (DFS) 遍歷圖，並移除遍歷過的邊。如果遍歷完畢後，鄰接矩陣中仍然存在邊，則圖中存在環，因此不是樹。
複雜度分析
- 時間複雜度: O(n + V^2)，其中 n 是邊的數量，V 是節點的數量。建立鄰接矩陣需要 O(n) 時間，DFS 遍歷需要 O(V + E) 時間，其中 E 是邊的數量，最壞情況下 E = V^2。
- 空間複雜度: O(V^2)，主要用於儲存鄰接矩陣
a。
程式碼
#include <iostream>
#include <sstream>
using namespace std;
int a[101][101],n,x,y,w,p,used[101],t;
string test;
void dfs(int xx,int yy){
a[xx][yy]=a[yy][xx]=0;
for(int i=0;i<101;++i){
if(a[xx][i])
dfs(xx,i);
if(a[i][yy])
dfs(i,yy);
}
}
int main(){
cin.sync_with_stdio(false), cin.tie(0);
cin >> n;
getline(cin,test);
while(n--){
for(int i=0;i<101;++i){
used[i]=0;
for(int j=0;j<101;++j)
a[i][j]=0;
}
w=0;
p=0;
getline(cin,test);
stringstream ss(test);
while(ss >> test){
x=y=0;
int i=0;
for (; test[i] != ','; i++)
x *= 10, x += int(test[i] - '0');
for (i++; i != test.size(); i++)
y *= 10, y += int(test[i] - '0');
a[x][y]=a[y][x]=used[x]=used[y]=1;
++w;
}
for(int i=0;i<101;++i)
if(used[i])
++p;
if(p!=w+1)
cout << "F\n";
else{
t=1;
for(int i=0;i<101;++i)
for(int j=0;j<101;++j)
if(a[i][j]){
dfs(i,j);
i=j=101;
}
for(int i=0;i<101&&t;++i)
for(int j=0;j<101&&t;++j)
if(a[i][j]){
cout << "F\n";
t=0;
}
if(t)
cout << "T\n";
}
}
}