Help needed , don't know one is wrong other is correct? [ Graph Problem 10 ]

help
,
1 
#define maxN 21
#define MAX 10000

vector<pii> adj[MAX];  // vector of pair <cost , node>
int vis[MAX];
lli level[MAX];
lli LCA[MAX][maxN];

void dfs(lli src , lli lvl , lli parent)
{
    level[src] = lvl;
    LCA[src][0] = parent;
    vis[src]=1; //works fine if i take vis array
    
    for(auto child : adj[src])
    {
        if(!vis[child.S])  // <------
            dfs(child.S , lvl+1 , src);
    }
}

// call this -
dfs(1,0,-1)

same but if condition with parent

#define maxN 21
#define MAX 10000

vector<pii> adj[MAX];  // vector of pair <cost , node>
int vis[MAX];
lli level[MAX];
lli LCA[MAX][maxN];

void dfs(lli src , lli lvl , lli parent)
{
    level[src] = lvl;
    LCA[src][0] = parent;

    for(auto child : adj[src])
    {
        if(child.S != parent)  // <------
            dfs(child.S , lvl+1 , src);
    }
}

// call this -
dfs(1,0,-1)

//It shows RE or comand signal 11

Help @galencolin @aneee004

2

Wait first correct your problem - is it a Graph or is it a tree? If it is graph with cycle then second code is definitely wrong.

3

Yes it is graph with cycle too.

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

4

But why ?

5

Then definitely second code is wrong…the consider a simple graph:
1-2, 2-3, 3-1
If you call dfs from node 1, and say you visit 2, then from 2 you visit 3 then from 3(whose parent is 2) you again visit 1 and you encounter infinite loop or Signal 11 error.
But I don’t think LCA is defined for graphs with cycle.

3 Likes
6

If it is a graph like you said then the 2nd code is wrong as it would revisit the nodes already visited as one node can have more than one immediate parent.

consider,
1->2
1->3
2->3
These are the edges.
here you start with 1 and say it first goes to 2.
2 ignores 1 as it is parent and goes to 3.
now 3 assumes only 2 is its parent according to your 2nd code. whereas even 1 is 3’s parent.

1 Like
7

Ok , now i understand , means this parent wala kaam only works in case of tree , right ?

2 Likes
8

Yes it works for tree only…how will you define LCA for graphs??

1 Like
9

LMAO , , ,no no I know that , but thanks .