商競103M-P31是否為樹(CPP版參考)

這是依商業技藝競賽程式103年模擬題第3題子題1稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料{0<n<10}，接著每組資料一列
每列是一個圖形的所有「邊」以空白隔開 ,每一個「邊」是由兩數字以逗號連接
判斷這個圖形是否為一棵樹，是印T否印F

參考程式碼：
/*
b517: 是否為樹-商競103 標籤 : dfs tree
這是 103年商業技藝競賽模擬題的 P31題，原題中對樹的描述就先省略了。
給一個圖形的邊的資訊，判斷是否為一棵樹？
輸入說明 ： 每組測資檔的第1列為一個數字 n ，代表以下有 n 列，每列為一個圖形的相鄰節點(邊)的資訊：
         每列中的所有邊皆由 i,j 表示，邊與邊之間以空格隔開， 0<=i,j <=80， i及j為相鄰的兩節點編號，以「,」連接i,j不含空格
輸出說明 ： 對於每一個圖形輸出一列，判斷其是否為一棵樹，若是則輸出 T 、否則輸出 F
*/
#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
const int MaxN = 80;  // 0~80
int val(string t)  //將字串的數字轉為數值
{
  int k=t.size();
  int i,v=0;
  for(i=0; i<k; ++i)
    if(t[i]>='0' && t[i]<='9')
   v = v*10 + t[i]-'0';
  return v;
}
bool adj[MaxN+5][MaxN+5] , nd[MaxN+5];
void dfs(int u)
{
nd[u] = false;   // 訪過的設為 false
for(int v=0; v<=MaxN; ++v)
{
if( adj[u][v]==true && nd[v]==true ) // 有相連且沒訪過
  dfs(v);
}
}
int main()
{
   int i,n;
   string line,s;
   cin >>n; getline(cin,line);
   while(n--)
   {
int vn=0 , en=0;  // node , edge 節點數、邊數
getline(cin,line);
istringstream  sin(line);  // 一整列轉成 串讀 
int st;
while( sin >> s) //以空格隔開 讀一個邊的字串 s
{
++en;
   int p=s.find(',');
   int x=val(s.substr(0,p)) , y=val(s.substr(p+1));
   adj[x][y] =  adj[y][x] = true;
   nd[x] = nd[y] = true;
   st = x;  // start node
}
      // 建好 adj 及 nd 兩個表後，以下判斷是否為樹
      for(i=0; i<=MaxN; ++i) 
   if(nd[i]) ++vn;  //計算節點數
      if( vn != en+1 ) { cout << "F" << endl; continue; } //節點數=邊數+1 ?
      dfs( st ); //從節點 st 開始 dfs ，有走過的 nd[ ]設為 false
      bool conn=true;
      for(i=0; i<=MaxN; ++i)
 if(nd[i])  { conn=false;  break; } //有某一節點沒訪過
      if(conn)  cout << "T" << endl;
      else cout << "F" << endl;
  }
  return 0;      
}
/*
範例輸入 ： 
4
6,8 5,3 5,2 6,4 5,6 1,2 2,0
8,1 1,3 6,2 8,10 7,5 1,4 7,8 7,6 8,0
3,8 6,8 6,4 5,3 5,6 8,2 2,0
1,0 4,3 1,2 
範例輸出:
T
T
F
F

*/