大神的世界

Tree 的判斷方式

1. vertex = edge +1

2. 任意兩點存在一條路徑

另外，因為任兩點間的路徑必定會經過 root

因此，條件 2 可解釋成每一個 node 往上 trace 必定到 root

為了加速，程式中使用 toRoot[ i ] 紀錄 Vi 是否能到 root

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int edge;
    int vertex_number;

    int vertex[1001];
    bool toRoot[1001];

    int root;
    int u, v, tmp, len;
    bool isTree;

    while(cin >> edge && edge){

        memset(vertex, 0, sizeof(vertex));
        memset(toRoot, 0, sizeof(toRoot));
        isTree = true;
        root = 0;
        vertex_number = 1; // root 

        for(int i = 0; i<edge; i++){
            cin >> u >> v;
            vertex[v] = u;
        }

        
        for(int i = 0; i<1001; i++){
            if(vertex[i]){
                vertex_number++;

                tmp = i; len = 0;
                while(vertex[tmp]){

                    tmp = vertex[tmp];
                    if(toRoot[tmp]){
                        toRoot[i] = true;
                        break;
                    }

                    len ++;

                    if(len > edge){  // 必免 loop 或 cycle
                        isTree = false;  
                        break;
                    }
                }

                if(!root)
                    root = tmp; 
                else if(!toRoot[tmp] && tmp != root){
                    isTree = false;
                    break;
                }

            }
        }

        if(!isTree || vertex_number != edge+1)
            cout << 'n' << endl;
        else
            cout << 'y' << endl;
    }
    return 0;
}