[UVA] 599 - The Forrest for the Trees

題目連結

題意：

給你一堆邊，問你有幾棵tree, 幾個acorn
tree就是有點有邊的連通圖，
acorn就是單單一個點，沒有任何邊。

--------------------------------------------------

我的作法：

因為題目先給邊再給點，所以我先把邊都先存起來，

讀點的時候才去將點都做編號，例如A編號為65，B編號為66

然後再去處理邊，如果有一條邊A-B，那就將node[65]連接node[66]，

都處理好了後，就DFS囉!

一次DFS就是一棵樹，

幾次DFS就是幾棵樹，

acorn則是判斷該node沒有任何連接其他node就是acorn

--------------------------------------------------

程式碼：

/* 題目: UVa 599 - The Forrest for the Trees

 * Language: C++

 * Created on: 2015年12月4日

 *   Author: hanting

 */

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

vector<string> edge;

vector<vector<int> > node;

vector<bool> visit;

int id[123];

void ReadAllEdge()

{

    edge.clear();

    string str;

    while(getline(cin, str) and str[0] != '*')

    {

        string e = "";

        char *pch = strtok((char*)str.c_str(), "(, )");

        e += pch;

        pch = strtok(NULL, "(, )");

        e += pch;

        edge.push_back(e);

    }

}

void ReadAllNode()

{

    string str;

    getline(cin ,str);

    int num = 0;

    for(int i = 0; i < str.size(); i++)

    {

        if(isalpha(str[i]))

        {

            id[str[i] ] = num++;

        }

    }

    visit.assign(num, 0);

    node.assign(num, vector<int>());

}

void ConnectSingleEdge(int a, int b)

{

    node[a].push_back(b);

    node[b].push_back(a);

}

void ConnectAllEdge()

{

    for(int i = 0; i < edge.size(); i++)

    {

        string tmp = edge[i];

        ConnectSingleEdge(id[tmp[0] ], id[tmp[1] ]);

    }

}

void DFS(int cur)

{

    for(int i = 0; i < node[cur].size(); i++)

    {

        int tmp = node[cur][i];

        if(!visit[tmp])

        {

            visit[tmp] = 1;

            DFS(tmp);

        }

    }

}

int main()

{

    int testCase = 0;

    cin >> testCase;

    cin.get();

    while(testCase--)

    {

        ReadAllEdge();

        ReadAllNode();

        ConnectAllEdge();

        int treeCnt = 0;

        int acorn = 0;

        for(int i = 0; i < node.size(); i++)

        {

            if(!visit[i] and node[i].size())

            {

                treeCnt++;

                DFS(i);

            }

        }

        for(int i = 0; i < node.size(); i++)

        {

            if(!node[i].size()) acorn++;

        }

        cout << "There are " << treeCnt << " tree(s) and " << acorn << " acorn(s)." << endl;

    }

    return 0;

}