Just a Graph solution codechef

Just a Graph solution codechef

You are given an undirected graph with NN nodes (numbered 11 through NN). For each valid ii, the ii-th node has a weight WiWi. Also, for each pair of nodes ii and jj, there is an edge connecting these nodes if jiWjWij−i≠Wj−Wi.

Find the number of connected components in this graph.

Input Format Just a Graph solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers W1,W2,,WNW1,W2,…,WN.

Output Format Just a Graph solution codechef

For each test case, print a single line containing one integer — the number of connected components in the graph.

Constraints

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • |Wi|109|Wi|≤109 for each valid ii
  • the sum of NN over all test cases does not exceed 21052⋅105

Subtasks Just a Graph solution codechef

Subtask #1 (30 points):

  • N103N≤103
  • the sum of NN over all test cases does not exceed 21032⋅103

Subtask #2 (70 points): original constraints

Sample Input 1 

2
2
1 2
2
2 1

Sample Output 1  Just a Graph solution codechef 

2
1

Explanation

Example case 1: For i=1i=1 and j=2j=2, we have 21=212−1=2−1, therefore there are no edges in the graph and there are two connected components.

Example case 2: For i=1i=1 and j=2j=2, we have 21122−1≠1−2, therefore there is an edge between 11 and 22, the graph is connected, so there is only one connected component.

Leave a Comment