Relatives Meeting

Count the number of relatives in the same group as a given person based on relationship pairs

Understand the Problem

Problem Statement

Relatives Meeting: There is a village festival happening in which several groups of relatives meet every year. Each person is allocated an identifier which is a positive integer.
N pairs of relatives identifiers are passed as input. Then finally given a person's identifier I, the program must print the count of the relatives C in the group of the person with the identifier I.

Constraints

1 ≤ N ≤ 10000
1 ≤ I ≤ 1000000
Person identifiers are positive integers
Relationships form undirected, transitive groups
Each pair represents a direct relationship between two people

Examples

Example 1

Input

Output

Explanation

10, 20, 30, 40 form a relative group (connected through relationships: 10-20, 30-20, 40-10). 55, 35, 22 form another relative group. So the count of relatives for the person with identifier 40 is 4.

Example 2

Input

Output

Explanation

All people (1, 2, 3, 4) form one group through transitive relationships. The count for person 2 is 4.

Solution

#include <stdio.h>
#include <stdlib.h>

#define MAX_PEOPLE 1000000

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

void init_union_find(int max_id) {
    for (int i = 1; i <= max_id; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // Path compression
    }
    return parent[x];
}

void union_sets(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    
    if (root_a != root_b) {
        // Union by rank
        if (rank[root_a] < rank[root_b]) {
            parent[root_a] = root_b;
        } else if (rank[root_a] > rank[root_b]) {
            parent[root_b] = root_a;
        } else {
            parent[root_b] = root_a;
            rank[root_a]++;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    int max_id = 0;
    int pairs[10000][2];
    
    // Read relationships and track max identifier
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &pairs[i][0], &pairs[i][1]);
        if (pairs[i][0] > max_id) max_id = pairs[i][0];
        if (pairs[i][1] > max_id) max_id = pairs[i][1];
    }
    
    init_union_find(max_id);
    
    // Union all related pairs
    for (int i = 0; i < n; i++) {
        union_sets(pairs[i][0], pairs[i][1]);
    }
    
    int target;
    scanf("%d", &target);
    
    // Count people in the same group as target
    int target_root = find(target);
    int count = 0;
    
    for (int i = 1; i <= max_id; i++) {
        if (find(i) == target_root) {
            count++;
        }
    }
    
    printf("%d\n", count);
    
    return 0;
}

Time:O(N α(N)) where α is the inverse Ackermann function (nearly constant)

Space:O(MAX_PEOPLE) where MAX_PEOPLE is the maximum person identifier

Approach:

C Solution Explanation:

init_union_find(): Initializes each person as their own parent with rank 0
find(): Finds the root of a person with path compression for efficiency
union_sets(): Merges two groups using union by rank optimization
Main Logic:
- Read all relationships and track the maximum person identifier
- Initialize union-find structure
- Union all related person pairs
- Find the root of the target person
- Count all people who share the same root (same group)

The solution handles the transitive nature of relationships efficiently.

Visual Explanation

Loading diagram...

All Problems