In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.
We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.
Input Format:
Input will consist of three parts, viz.
1. The total number of people on the social network (N)
2. Queries
· C I J, connect I and J
· Q 0 0, print the number of communities with even member-count -1 will represent end of input.
Output Format:
For each query Q, output the number of communities with even member-count.
Constraints:
1<=N<=10^6
1<=I, J<=N
Input:
5
Q 0 0
C 1 2
Q 0 0
C 2 3
Q 0 0
C 4 5
Q 0 0
-1
Output:
0
1
0
1
Explanation:
For first query there are no members in any of the groups hence answer is 0. After C 1 2, there is a group (let’s take it as G1) with 1 and 2 as members hence total count at this moment is 1. After C 2 3 total members in G1 will become {1, 2, 3} hence there are no groups with even count. After C 4 5 there formed a new group G2 with {4, 5} as members, hence the total groups with even count is 1.
Solution: In C
Solution: In Java
Also Checkout