FRNDCIRC - FRIEND CIRCLE
Lucy has made too many friends but she does not know how many friends are in her circle. Assume that every relation is mutual. If Lucy is Patty's friend, then Patty is also Lucy's friend. Your task is to help Lucy in keeping track of each person's circle size.
Input Specification
The first line of input contains one integer T (T<=10) specifying the number of test cases to follow. Each test case begins with a line containing an integer N (N<=100000), the number of new relations. Each of the following N lines contains couple of strings denoting the names of two people who have just formed relation, separated by a space. Names will have no more than 20 characters.
Output Specification
Print a line containing one integer, the number of people in the combined circle of two people who have just become friends.
Input
1 4 Lucy Patty Patty Alice Alice Mira Tiffany Jayden
Output
22 3 4 2
hide comments
|
giabao1605:
2023-04-02 14:28:31
scario problemo Last edit: 2023-04-02 14:30:17 |
|
aseye_15:
2023-01-21 12:40:04
Sneaky bastard but nice solution, AC in one gooo!!!!! |
|
cynder:
2020-07-07 21:41:19
Easy problem, WA in 1st go. Last edit: 2020-07-07 21:51:34 |
|
transonviet:
2020-01-17 15:23:03
Easy dsu problems AC in one go using map still got AC |
|
ichigo_1:
2019-09-25 16:42:14
It is a nice problem. A good practice for a disjoint set union. |
|
satyabrat35:
2019-02-09 14:34:43
Use unordered_map instead of map |
|
anirudnits:
2018-06-14 20:08:49
thanks @naruto09. |
|
memoize_giri:
2018-06-08 19:14:51
Replaced Scanner class with BufferedReader..
|
|
nadstratosfer:
2017-10-19 01:50:35
Easier to AC in Py2 than in PyPy because of TL on one of the testfiles being so absurdly small that interpreter launch time actually matters. Always frustrating having to wrestle against such issues, but in the end got an idea that cut my runtime by a whole second and provided a valuable lesson. What doesn't kill you, makes you stronger =) Last edit: 2018-01-29 23:28:11 |
|
gauravseta:
2017-02-22 12:14:53
I am using Java ..it is getting TLE . tried with ConcurrentHashMap and HashMap both. Someone pls help. using Map correct DS for this problem?
|
| Added by: | Vamos |
| Date: | 2013-06-26 |
| Time limit: | 0.100s-1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
RSS