CAM5  prayatna PR
help the Prayatna pr team
Well, the annual technical symposium of Department of Computer Technology is around the corner. All that we need, to make it a grand success is Publicity among the peer groups ( ofCourse the sponsors too :P ). We decided to share the job between the student groups. As per the plan we decided to meet people in person and influence them to attend Prayatna. But to meet them we have to go to various student groups. To do so, we had to cut our classes. But being studious. students refused to cut more classes. Instead of meeting every one in person we decided to meet few people such that the person to whom we pass the news will spread it to all his friends. And those friends will pass it to other friends and so on. Your task is to find the number of people to be met by the organizers to spread the news.
Caution: Large I/O
Input
First line of input is 't'  Test cases. Follwed by N, the number of peers in the testcase ( 0 to N1 ). followed by the number of friend description 'e'. Following are 'e' descriptions of type "a b" denoting 'a' friends with 'b'. If 'a' is friends with 'b' then 'b' is friends with 'a'.
Output
Output contains t line, the number of people, the organizers have to meet in person for each test case.
Example
Input: 2 4 2 0 1 1 2 3 0 Output: 2 3
Explanation
case 1 : 0 is friends with 1; 1 is friends with 2; so if we pass the news to 0 & 3, news will pass it to the entire N peers.
case 2 : no one is friends with any one. So we have to meet every one in person.
Constraints
t = 10
2 <= N <= 100000
0 <= e <= N/2
hide comments
mreagle1:
20181111 20:21:44
Easy problem when use DSU. 

ihg_2_26:
20180828 21:41:15
Do not consider spojtoolkit for this question 

kbspoj97:
20180813 12:09:34
For those guys who are facing TLE in java, try to use a customized Reader class for I/O.


srvptk97:
20180711 18:21:20
Why DFS , with Disjoint Sets it is much easier and faster!! 

cyber_sm0ke:
20180702 17:32:02
I Am using simple DFS to calculate connected component and storing graph in vector< vector<ll> > g , I am facing TLE .


ankur314:
20180509 09:20:18
simple BFS will do 

ameyanator:
20180317 20:05:19
Super easy question. Just need to find the connected components in the graph! 

badasshackme:
20180311 23:16:04
dfs, but you should not use NxN array for edges, bcz you will hit N = 10^5 limit. Use map or vector in C++ to store only edges. 

nadstratosfer:
20180219 05:50:11
Random blanklines in input, make sure to ignore these when solving in Python else NZEC. 

jee_333:
20180203 18:18:34
why java solution is not feasible or showing always TLE??

Added by:  karthikeyan 
Date:  20120111 
Time limit:  0.376s0.662s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 