Just a Graph Problem Code: JAG Codechef Solutions

 

Just a Graph Problem Code: JAG

Submit

Read problem statements in Mandarin, Bengali, Russian, and Vietnamese as well.

You are given an undirected graph with N$N$ nodes (numbered 1$1$ through N$N$). For each valid i$i$, the i$i$-th node has a weight Wi$W_i$. Also, for each pair of nodes i$i$ and j$j$, there is an edge connecting these nodes if j−i≠Wj−Wi$j-i\ne W_j-W_i$.

Find the number of connected components in this graph.

Input Format

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains N$N$ space-separated integers W1,W2,…,WN$W_1,W_2,\dots ,W_N$.

Output Format

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

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 1≤N≤105$1\le N\le {10}^5$
• |Wi|≤109$|W_i|\le {10}^9$ for each valid i$i$
• the sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$

Subtasks

Subtask #1 (30 points):

• N≤103$N\le {10}^3$
• the sum of N$N$ over all test cases does not exceed 2⋅103$2\cdot {10}^3$

Subtask #2 (70 points): original constraints

Sample Input 1 

2
2
1 2
2
2 1

Sample Output 1 

2
1

Explanation

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

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

Author:5★angeshs

Date Added:25-08-2021

Time Limit:0.5 secs

Source Limit:50000 Bytes

Languages:CPP14, C, JAVA, PYTH 3.6, CPP17, PYTH, PYP3, CS2, ADA, PYPY, TEXT, PAS fpc, NODEJS, RUBY, PHP, GO, HASK, TCL, PERL, SCALA, LUA, kotlin, BASH, JS, LISP sbcl, rust, PAS gpc, BF, CLOJ, R, D, CAML, FORT, ASM, swift, FS, WSPC, LISP clisp, SQL, SCM guile, PERL6, ERL, CLPS, ICK, NICE, PRLG, ICON, COB, SCM chicken, PIKE, SCM qobi, ST, SQLQ, NEM

Solution in C++

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main(){

ll t;cin>>t;

while(t--){

ll n;cin>>n;

ll a[n];

ll ans=0;

map<int,int> mp;

for(int i=0;i<n;i++){

cin>>a[i];

mp[a[i]-i-1]++;

if(mp[a[i]-i-1]==1){

ans++;

}

}

if(mp[a[0]-1]==n){

cout<<n<<endl;

}

else{

cout<<1<<endl;

}

}

return 0; }