判斷一個圖是否構成樹
問題
給定一個無向圖，判斷該圖是否構成樹，
輸入
輸入有若干測驗樣例，第一行是測驗樣例個數，接下來若干測驗樣例， 每個測驗樣例的第一行是結點數n，而且結點用1,2,…, n編號， 第二行是邊數m，接下來是 m個結點對，
輸出
如果一個圖是樹，則列印“YES"，否則列印"NO"，每個輸出占一行，
輸入樣例
3
3
2
1 2
2 3
3
3
1 2
2 3
1 3
3
1
2 3
輸出樣例
YES
NO
NO
思路：
樹是沒有簡單回路的連通無向圖
判斷方式：
- 無向圖是連通的（用warshall演算法判斷）
- 沒有簡單回路（根據樹的性質：帶有n個結點的樹含有n-1條邊）
代碼實作
#include <stdio.h>
//warshall 演算法 //傳遞閉包
void warshall(int matrix[][100],int size){
for(int j = 0; j < size; j ++){
for(int i = 0; i < size; i ++){
if(matrix[i][j] == 1){
for(int k = 0; k < size; k ++){
matrix[i][k] = matrix[j][k] || matrix[i][k];
}
}
}
}
}
int main(){
int num;
scanf("%d",&num);//回圈次數
for(int m = 0;m < num; m++){
int flag = 1;
int mat[100][100] = {0};
int v,e;
scanf("%d",&v);//點數
scanf("%d",&e);//邊數
//輸入所有邊
for(int i = 0; i < e; i++){
int j,k;
scanf("%d",&j);
scanf("%d",&k);
mat[j-1][k-1] = 1;
mat[k-1][j-1] = 1;
mat[i-1][i-1] = 1;
}
//1 判斷是否有回路（樹的性質）
if(v-e!=1){
flag = 0;
}
//2 判斷是否連通（warshall 傳遞閉包）
warshall(mat, v);
for(int j = 0; j < v; j++){
for(int k = 0; k < v; k++){
if(mat[j][k]!=1){
flag = 0;
}
}
}
if(flag==0){
printf("NO\n");
}else{
printf("YES\n");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/33489.html
標籤：C
上一篇：【學習筆記】C語言習題：有n個人圍成一圈，順序排號。從第一個人開始報數（從1到3報數），凡報到3的人退出圈子，問最后留下的是原來第幾號的那位。
下一篇：C 實戰練習題目7