ZeroJudge D831: 畢業旅行

多年來友情的羈絆，終於將在這畢業的季節開花結果。

這幾天，班上同學們無時無刻都熱烈討論著畢業旅行的地點。

小明說，如果要去六福村，可以順便去小人國；

小美說，如果去了恆春的話，墾丁就在幾十公里外了，一定也要去玩；

小華表示，小鬼湖跟大鬼湖好像很近，似乎都是很有趣的地方。

身為班長，聽到同學這麼多「去了哪裡也可以去哪裡」的資訊後，你決定要為班上的同學們，找到一個能玩最多景點的畢業旅行。

範例測資

範例輸入範例輸出
有多組測試資料，以 EOF 結束。
每組測試資料的第一行有兩個正整數 N (N <= 1000000) 和 M (M <= 100000)，表示景點有 N 個，編號為 0～N-1。
接下來有 M 行，每行有兩個整數 a 和 b (0 <= a、b < N)，表示去了 a 的同時也可以去 b (反過來也一樣）。		輸出一個數字，表示畢業旅行最多可以玩的景點數量。
6 4
0 1
2 3
1 3
5 4
1000000 0
1000000 1
0 999999		4
1
2
ZeroJudge D831 範例測資

解題思路

使用 Map 來紀錄每一個景點的最底層，所有預設值為 -1。

宣告一個函式 findEnd，需要一個參數 N，如果 N == -1 || Map[N] == -1，return N。如果 Map[N] == N，return N。否則 return findEnd(Map[N])。

輸入資料時，如果兩個都沒有紀錄，則將右邊的設定為左邊的。如果兩個人都有紀錄，將其中一個的 Map 值設為 findEnd(另一個人)。如果是一個有一個沒有，則將沒有的人的 Map 值設定成 findEnd(另一個人)。

收完資料之後宣告一個 map<int, int>ans，代表要紀錄的最多景點數。跑一個從 0 到 N-1 的迴圈，如果 findEnd(目前數字) != -1，則將 ans[findEnd(目前數字)]++，並且判斷最大值。答案就是最大值。

範例程式碼－ZeroJudge D831: 畢業旅行

#include <iostream>
#include <map>
using namespace std;

int N, M;
map<int, int>MAP;

int findEnd(const int N) {
    if (N == -1 || MAP[N] == -1) return -1;
    if (MAP[N] == N) return N;
    return findEnd(MAP[N]);
}

void graduate(const int a, const int b) {
    if (MAP[a] == -1 && MAP[b] == -1) {
        if (b == 0) {
            MAP[a] = b;
            MAP[b] = b;
        }
        else {
            MAP[a] = a;
            MAP[b] = a;
        }
    }
    else if (MAP[a] != -1 && MAP[b] != -1) {
        if (findEnd(MAP[b]) == 0) MAP[findEnd(a)] = 0;
        else MAP[findEnd(b)] = findEnd(a);
    }
    else {
        if (MAP[a] != -1) MAP[b] = findEnd(a);
        else MAP[a] = findEnd(b);
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N >> M) {
        if (M == 0) {
            cout << "1\n";
            continue;
        }
        MAP.clear();
        for (int i = 0; i<N; i++) MAP[i] = -1;
        for (int i = 0; i<M; i++) {
            int a, b;
            cin >> a >> b;
            graduate(a, b);
        }
        map<int, int>ans;
        int max = -999;
        for (int i = 0; i<N; i++) {
            const int tmp = findEnd(i);
            if (tmp != -1) ans[tmp]++;
            if (ans[tmp] > max) max = ans[tmp];
        }
        cout << max << "\n";
    }
}

//ZeroJudge D831
//Dr. SeanXD

我的宇恆，畢業快樂！

標籤

相關文章

發佈留言