# Help needed in LeetCode medium problem

I am solving this problem using DSU.
But it fails on this test case, I can’t find the mistake.
Is my logic incorrect or some bug?
I saw that this can be easily solved using recursion(DFS) and queue(BFS).

class Solution
{
public:
vector<int> parent;

void makeSets()
{
for (int i = 0; i < parent.size(); i++)
{
parent[i] = i;
}
}

int findSet(int a)
{
if (a == parent[a])
{
return a;
}
return parent[a] = findSet(parent[a]);
}

void unionSets(int a, int b)
{
a = findSet(a);
b = findSet(b);
if (a != b)
{
parent[a] = b;
}
}

bool canReach(vector<int> &arr, int start)
{
parent.assign(arr.size(), 0);
makeSets();
int n = arr.size();
vector<int> zeroIndices;

for (int i = 0; i < n; i++)
{
int x = i + arr[i];
int y = i - arr[i];
if (arr[i] == 0)
{
zeroIndices.push_back(i);
continue;
}
if (0 <= x && x <= n - 1)
{
unionSets(i, x);
}
if (0 <= y && y <= n - 1)
{
unionSets(i, y);
}
}

for (auto i : zeroIndices)
{
if (findSet(i) == findSet(start))
{
return true;
}
}
return false;
}
};


Any help would be great.
Thanks

@ssrivastava990 what do you think?

Bro frankly , I don’t know DSU so much , @aneee004 will help .

If u have any problem in both of them i will surely help .

1 Like

There is no submission via DSU , is it really solvable by DSU ?
some user also said this - > HERE

I too read that, but DSU was my first intuition, so i just wanted to make sure if it can be solved.
Thanks anyway brother.

what made u think to solve this problem by DSU share your intutuion

if we can reach a zero value index by some start point, it means they must be connected,
So i thought why not use union set to combine the connected indices and and then find set to check if they belong to the same group or not.

Look at this test case
[0,1,3,3]
2
The 1st index is connected to the 0th and the 2nd index separately, in your code you connect the 0th index and the 2nd index too, giving you a false positive.

You cannot use DSU here, because the edges are directed. Lets say j = i + A[i] for some i. This means you can get from i to j, but it is not necessarily true that you can get from j to i too. Because i \neq j \pm A[j].

Example: The beautiful one pointed out by @preyam

[UPD]: My solution with dfs.

Code
class Solution {
vector<bool> vis;
bool dfs(vector<int> &A, int u) {
if(A[u] == 0) return true;
vis[u] = 1;
for(int v : adj[u]) if(not vis[v])
if(dfs(A, v)) return true;
return false;
}
public:
bool canReach(vector<int>& A, int start) {
int n = A.size();
vis.assign(n, false);
for(int i = 0; i < n; i++) {
if(i + A[i] < n)