ZeroJudge A445: I don't have friends

My friends are few, but my friends' friends are my friends too!

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains three positive integers N, M, and Q (N ≤ 10000, M ≤ 10000, Q ≤ 100000), representing N people, M friendship relations, and Q queries.
The next M lines each contain two positive integers A and B (A, B ≤ N), representing that A and B have a friendship relationship.
The next Q lines each contain two positive integers P and Q (P, Q ≤ N).		Please output whether P and Q are friends. If they are, output ":)". Otherwise, output ":(".
5 3 2
1 2
2 5
3 4
1 5
1 3		:)
:(

Thought Process

Declare an array to represent the "root friend" of each person, with the initial value for everyone set to 0. If a person is encountered and their array value is 0, it means they haven't been recorded yet, so set their array value to themselves.

Declare a function findEnd to find the "root friend". It has one parameter N. If the array value of N is 0 or N itself, then return N; otherwise, return findEnd(arrayValue[N]).

When processing the data, set arrayValue[findEnd(B)] to findEnd(A). Finally, to check if P and Q are friends, verify if arrayValue[P] is equal to arrayValue[Q]. If they are the same, it means these two people are friends.

Sample Code－ZeroJudge A445: I don't have friends

#include <iostream>
using namespace std;

int MAP[870000] = {};

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

void line(const int a, const int b) {
    if (MAP[a] == 0) MAP[a] = a;
    if (MAP[b] == 0) MAP[b] = b;
    MAP[findEnd(b)] = findEnd(a);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    for (int i = 1; i<=N; i++) MAP[i] = 0;
    for (int i = 0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        line(a, b);
    }
    for (int i = 0; i<Q; i++) {
        int a, b;
        cin >> a >> b;
        if (findEnd(a) == findEnd(b)) cout << ":)\n";
        else cout << ":(\n";
    }
}

//ZeroJudge A445
//Dr. SeanXD
Tags

Related Posts

Comments