AKVHYD03 - India has a Plan 400 pts
There are "N" people in India. People in India can use "M" languages for talking to each other. The languages are given numbers from 1 to M. For every person, we have the list of languages he/she speaks. This list can be empty too. Indian government wants that every person should be able to talk to each other (directly or indirectly, i.e. they may use other people to translate languages to make them communicate). People also want this to happen and they are ready to learn the languages. The government will pay Rs. 1 to a person for learning one language. But the government wants to minimize the amount of money it spends. Can you tell what is the minimum amount of money government needs to spend such that every person can communicate with every other person (directly or indirectly).
Input
First line will contain two integers N and M. Then N lines will follow.
Each of the next N lines will contain the list of each person. At the beginning of the i-th line is integer Ki - the number of languages the i-th person knows. After this there will be Ki integers on the same line, the list of the languages the i-th person knows. A person may know zero languages.
Output
Print a single integer - the minimum amount of money Indian government needs to spend so that every person can communicate with each other (directly or indirectly).
Constraints
1 <= N, M <= 100
0 <= Ki <= M
Example
Input: 5 5 1 2 2 2 3 2 3 4 2 4 5 1 5 Output: 0
Input: 8 7 0 3 1 2 3 1 1 2 5 4 2 6 7 1 3 2 7 4 1 1 Output: 2
Input: 2 2 1 2 0 Output: 1
Explanation
In the second sample case, person 1 can learn language 2, and person 8 can learn language 4.
In the third sample case, person 2 must learn language 2.
hide comments
nadstratosfer:
2018-05-25 09:41:12
This wouldn't be out of place in the classical section, IMHO. Fun problem. |
Added by: | Ankit Kumar Vats |
Date: | 2013-08-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |