大神的世界

你覺得能從我這得到什麼其他提示嗎？ (應該不行)

1.  點數 - 1 是否 = 邊數

2.  經過一次 DFS 後 (由 main 呼叫) ，是否所有點都走過

如果 DFS 由 main 多次呼叫，代表此圖不為連通圖 (好ㄅ，這應該算是額外的提示...）

#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

constexpr int MAX_NODE_NUM = 81;

bool setAdjMatrix(bool _matrix[][MAX_NODE_NUM], bool _visited[])
{
    string edges;
    getline(cin, edges);
    istringstream iss(edges);

    int edgesNum = 0;
    int vertexNum = 0;
    while(iss >> edges){
        int i;
        int n1 = 0;
        for(i = 0; edges[i] != ','; i+=1)
            n1 = n1*10 + edges[i]-'0';

        int n2 = 0;
        for(i = i+1; i<edges.size(); i+=1)
            n2 = n2*10 + edges[i]-'0';

        if(!_matrix[n1][n2]){
            _matrix[n1][n2] = _matrix[n2][n1] = 1;
            edgesNum += 1;
        }

        if(_visited[n1]){
            _visited[n1] = false;
            vertexNum+=1;
        }
        if(_visited[n2]){
            _visited[n2] = false;
            vertexNum+=1;
        }
    }

    if(vertexNum > 1 && vertexNum-1 != edgesNum) return false;
    return true;
}

void DFS(const bool _matrix[][MAX_NODE_NUM], bool _visited[], const int &_idx)
{
    _visited[_idx] = true;

    for(int i = 0; i<MAX_NODE_NUM; i+=1)
        if(!_visited[i] && _matrix[_idx][i])
            DFS(_matrix, _visited, i);
}

int main()
{
    int case_num;
    while(cin >> case_num){
        cin.ignore();
        for(int i = 0; i<case_num; i+=1){

            bool visited[MAX_NODE_NUM];
            for(bool &b: visited)
                b = true;

            bool adj_matrix[MAX_NODE_NUM][MAX_NODE_NUM] = {};
            if(!setAdjMatrix(adj_matrix, visited)){
                cout << "F" << endl;
                continue;
            }

            bool status = true;
            for(int j = 0; j<MAX_NODE_NUM; j+=1){
                if(!visited[j]){
                    DFS(adj_matrix, visited, j);
                    break;
                }
            }

            if(status && all_of(&visited[0], &visited[MAX_NODE_NUM-1], [](bool x){ return x; }))
                cout << "T" << endl;
            else
                cout << "F" << endl;
        }
    }

    return 0;
}