Beginner
1. Consecutive Prime Sum2. Alpha Numeric Sorting3. Longest Progressive Sequence4. Divine Divisor5. Forest Fire6. Minimum Distance7. Saving for a rainy day8. Online Communities Even Groups9. Coin Distribution10. Bank Compare11. Counting Rock Samples12. Collecting Candies13. Game Of Primes14. Kth Largest Factor15. Jumble With Numbers16. Philand Coins17. Reverse Gear18. String Rotation19. The Vita Sum20. Mountain Peak Sequence21. LAZY STUDENT22. LOGIC PYRAMID23. Super ASCII String Checker24. Min Product Array25. String Of Brackets26. Exchange Of Digits27. Marathon Winner28. Common Steps29. Swayamvar30. Digit Pairs31. Dole Out Cadbury32. Petrol Pump33. Grooving Monkeys34. Death BattleOnline Communities Even Groups
LEVEL:Beginner
Description
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
Constraints:
1<=N<=10^6
1<=I, J<=N
Output Format
For each query Q, output the number of communities with even member-count
5 Q 0 0 C 1 2 Q 0 0 C 2 3 Q 0 0 C 4 5 Q 0 0 -1
0 1 0 1
10 C 1 2 Q 0 0 C 4 5 Q 0 0 C 7 8 Q 0 0 -1
1 2 3
6 Q 0 0 C 1 2 Q 0 0 C 2 3 Q 0 0 C 3 4 Q 0 0 -1
0 1 0 1
Login to see Discussion
Approach
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.
First we are creating array which represents the social media users
In order to get this lets take about example
there are total 5 users so
0 0 0 0 0
initially 1 and 2 are in same group so lets assign them a common number 1
1 1 0 0 0
then to print the even group we check entire array and keep count of numbers which are having common number then we check if the number is even we print the count
then it is given that 2 and 3 are common. Here we can see that 2 is already having 1 so we assing the same number to 3. Now the array becomes
1 1 1 0 0
Here there are no even groups so we print 0
then it is given that 4 and 5 are common . Here we can see that both are having 0 so we need to assing both of them a common value . Here 1 is assigned to previous one , so we increment the common number and assign 2 to them. Now the array is as follows
1 1 1 2 2
Here we can see that 2 is having a even group so we print 1 as there is only one even group
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution