ZeroJudge D831: Graduation Trip

Over the years, the bonds of friendship will finally blossom and bear fruit in this graduation season.

These days, classmates in the class are enthusiastically discussing the destination for their graduation trip at every moment.

Xiao Ming said that if we're going to Leofoo Village, we can also visit the Miniatures Museum.

Xiao Mei said that if we go to Hengchun, Kenting is just a few tens of kilometers away, so we have to go and play there too.

Xiao Hua said that Little Ghost Lake and Big Ghost Lake seem very close to each other, and both seem like very interesting places.

As the class monitor, after hearing so much information about "wherever you go, you can also go there," you decide to plan a graduation trip that allows your classmates to visit the most attractions possible.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
There are multiple sets of test data, and the input ends with EOF (End of File).
For each set of test data, the first line contains two positive integers, N (N ≤ 1000000) and M (M ≤ 100000), indicating there are N attractions numbered from 0 to N-1.
Following that, there are M lines, each containing two integers a and b (0 <= a, b < N). This indicates that if you visit attraction a, you can also visit attraction b (and vice versa).		Output a number representing the maximum number of attractions that can be visited during the graduation trip.
6 4
0 1
2 3
1 3
5 4
1000000 0
1000000 1
0 999999		4
1
2
ZeroJudge D831 Sample Test Case

Thought Process

Use a map to record the ultimate root of each attraction, with all initial values set to -1.

Declare a function findEnd that takes a parameter N. If N == -1 or Map[N] == -1, return N. If Map[N] == N, return N. Otherwise, return findEnd(Map[N]).

When entering data, if neither attraction has a record, set the right one to the left one. If both have records, set one of the map values to findEnd(the other one). If one has a record and the other does not, set the one without a record's map value to findEnd(the other one).

After collecting the data, declare a map ans to record the maximum number of attractions. Run a loop from 0 to N-1. If findEnd(current number) != -1, increment ans[findEnd(current number)]++ and check for the maximum value. The answer will be the maximum value found.

Sample Code－ZeroJudge D831: Graduation Trip

#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

我的宇恆，畢業快樂！

Tags

Related Posts

Comments