SPOJ.com - Problem FRNDCIRC

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

Submit solution!

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

hide comments

2013-12-24 19:09:46 Rishab Kalra
why am i getting wrong ans. my submission id is 10731242

2013-12-16 16:00:03 Arvind
Basic problem, but time limits make it very nice! :)

2013-12-16 08:47:35 Kevin Sebastian
my submision id 10671030 why am i getting sigsev fault

2013-07-25 14:29:00 Vikas Kushwaha
Time Limit make this one good> :)

2013-07-14 09:28:59 RAJDEEP GUPTA
Nice Problem. :)

2013-07-14 09:28:59 :D
Time limits like 0.1s are very iffy. I'm not sure for Cube, but on Pyramid they were blocking languages with slow startup. Don't change the problem now, but for future reference, rather try to do make 1s time limits and bigger test files.

PS. Problem itself is very nice. Thanks for putting it on SPOJ :)

2013-07-14 09:28:59 Vamos
@John snow : Try to approach differently.

Last edit: 2013-07-22 08:50:48

2013-07-14 09:28:59 P[_]/|/K
Thanks to the problem setter for decreasing the time limit.
It made me improve my solution.. :)

2013-07-14 09:28:59 John Snow
@saurabh kr vats,can you tell where my solution is giving wrong answer

2013-07-14 09:28:59 ss
@saurabh kr. vats plz tell me, is there may be more than one friend circle???

Last edit: 2013-06-27 18:10:43