ex_4.c

#include <stdio.h>

#define MAX_PEOPLE 100000

int parent[MAX_PEOPLE + 1];
int group_size[MAX_PEOPLE + 1];

void begin_group() {
    for (int i = 1; i <= MAX_PEOPLE; i++) {
        parent[i] = i;
        group_size[i] = 1;
    }
}

int find_by_path_compression(int person_num) {
    if (parent[person_num] != person_num) {
        parent[person_num] = find_by_path_compression(parent[person_num]);
    }
    return parent[person_num];
}

void groups_marger(int friend1, int friend2) {
    int root_friend1 = find_by_path_compression(friend1);
    int root_friend2 = find_by_path_compression(friend2);

    if (root_friend1 != root_friend2) {
        if (group_size[root_friend1] < group_size[root_friend2]) {
            parent[root_friend1] = root_friend2;
            group_size[root_friend2] += group_size[root_friend1];
        } else {
            parent[root_friend2] = root_friend1;
            group_size[root_friend1] += group_size[root_friend2];
        }
    }
}

int get_friends_count(int x) {
    int root = find_by_path_compression(x);
    return group_size[root] - 1;
}

int main() {
    int N, M;

    printf("Enter number of people (N) and number of frienships (M): ");

    if (scanf("%d %d", &N, &M) != 2 || N <= 0 || N > MAX_PEOPLE || M < 0) {
        printf("Invalid input.\n");
        return 1;
    }

    begin_group(); // Union Find

    printf("Please enter %d friendships. In every row: <person_num_1> <person_num_2>\n", M);

    for (int i = 0; i < M; i++) {
        int a, b;
        if (scanf("%d %d", &a, &b) != 2 || a < 1 || a > N || b < 1 || b > N) {
            printf("invalid friendship number: %d %d\n", a, b);
            continue;
        }
        groups_marger(a, b);
    }

    int query;
    while (scanf("%d", &query) != EOF) {
        printf("Enter the number of the person for whom you want to see the number of friends (or nter 0 to exit): ");
        if (query == 0) break;

        if (query < 1 || query > N) {
            printf("Invalid person name: %d\n", query);
        } else {
            printf("%d\n", get_friends_count(query));
        }
    }

    return 0;
}