Getting WA Just A Graph August LunchTime 2021

help
1 
#include<bits/stdc++.h>

using namespace std;

int main()
{
    long long t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        long long x;
        cin >> x;
        long long val = x - 1;
        bool connected = false;
        for(long long i = 1; i < n;i++){
            cin >> x;

            if(val != x - i - 1){
                connected = true;
                break;
            }
        }
        if(connected)cout << 1 << endl;
        else cout << n << endl;
    }
    return 0;
}
2

ur code seems incorrect

3

can you provide any testcase where it will fail?

4

yes i can but tell me whether u r sure about ur solution rather have u proved it?
I am attaching my comment , where I tried to explain my approach for a given test case
hope it will help,
1
4
1 2 3 3
for this test case answer will be 1 .
Explanation :
edge is between i and j if Wi-Wj not equal to i-j

this can be written as Wi-i not equal to Wj-j

so I calculate all the values Wi-i

for the input above array W[ ] is : 1 2 3 3
i: 1 2 3 4
Wi-i = 0, 0, 0 , 1

now the values 0 → indexes 1 2 3 cant have edges among them

but each of them (i.e 1,2,3) will be connected to 4

so the number of connected component is 1

// note answer is either n or 1.

1 Like
5

I have also done the same thing.
here val is weight of 1st index - 1

For remaining indices,
I am checking if weight of any index - index != val , then graph is connected, ans will be 1

if not for any index, graph is disconnected ans will be n

6

bro understood why are getting WA, u r breaking while u r taking input

store the input x in an array and do the same thing ur approach is correct

7

thanks bro

8

ur welcome :smiley: