UVa 10583

From Algorithmist
Jump to: navigation, search

10583 - Ubiquitous Religions[edit]

Summary[edit]

You must keep track of how many different possible religions people can have. You are only given information about which people have the same religion, not the religion that they actually practice.

Explanation[edit]

This can be solved as an Union Find problem. The reasoning is that the transitive property holds: if person X shares a religion with person Y, and person Y shares a religion with person Z, then person X shares a religion with person Z. We can use Union Find to keep track of this.

Implementations[edit]

Input[edit]

10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
100 1
1 2
3 5
1 2
2 1
1 2
2 1
1 2
0 0

Output[edit]

Case 1: 1
Case 2: 7
Case 3: 99
Case 4: 2