Need Help CSES Graph Problem: High Score

Блог пользователя Vedkribhu

Автор Vedkribhu, история, 6 лет назад, По-английски

Problem: Link I was using Bellman Ford to solve this. To detect a cycle in bellman ford we usually do one more pass on the edges (after n-1) passes and see if anything updated, if yes there is a cycle. But in this problem even if there is a cycle in graph but not a part of path between vertex 1 and n is tolerable. How to detect when to print -1?

Vedkribhu
6 лет назад
22

Комментарии (12)

Показать архивные | Написать комментарий?

HelloWorld

6 лет назад, скрыть # |

Run the Bellman-Ford Algorithm for the nth iteration and mark the nodes whose distance is changed. Now reverse the adjacency list and run a DFS from node 'n'. If at least one of the nodes marked is visible from n, then the answer is -1, else the answer is the maximum distance from 1 to n.

→ Ответить

sia

6 лет назад, скрыть # ^ |

Can you please explain the intuition behind doing this?

→ Ответить

Naithani

6 лет назад, скрыть # ^ |

Only to check that, does a positive cycle in the graph affects the 'nth' node, if it does, then it is sure that answer is -1, else answer is the max distance.

Ex:

7 7

1 2 1

2 7 1

1 6 -1

6 5 -1

5 4 -1

4 3 -1

3 1 5

here, the +ve cycle affects the 'nth' node.

But here,

8 9

1 2 1

2 3 1

3 4 1

4 2 1

1 8 1

5 8 1

5 6 1

6 7 1

7 5 1

it doesn't affect the nth node.

→ Ответить

peakyblinders

6 лет назад, скрыть # ^ |

Reason behind marking nodes whose distances are changed in the nth iteration — node which is marked is involved in the cycle. We will print -1 only when it is possible to reach to last node from the cycle. To check whether it is possible to reach to last node from the cycle, there are two ways 1) run dfs from every node which is marked (involved in cycle) and check whether is it possible to reach to nth node, if yes print — 1. 2)reverse the graph and check whether it is possible to reach to atleast one node which is marked from the last node, if yes print -1. Both ways give the same result but the 2nd method is fast. Please ask if you have any doubt(this is my first explanation, I apologize if my explanation is not clear).

→ Ответить

Sacharlemagne

3 года назад, скрыть # ^ |

The first approach can be optimized by inserting all those nodes into a queue and running a bfs. Depending on the data structure used to store the graph it can be simpler or more complicated than the second one. If there is an adjacency array for every node then the bfs is simpler, but for an array of edges the dfs is much simpler since there is no need to reverse the edges.

→ Ответить

matheusdacach

6 лет назад, скрыть # ^ |

← Rev. 3 →

what if the node (in the cycle and connected to n) is not connected to 1?
1 4 1
2 4 1
2 3 1
3 2 1
there's a cycle 2 — 3 — 2 and 2 is connected to 4 but even then, answer is still 1 (and not -1) because we can't go to that cycle

what I did was see everyone that could be in a path from 1 to n, if one of those nodes are in a cycle, answer is -1:

run dfs from 1 in original graph, mark everyone connected
run dfs from n in reversed graph, mark everyone connected
intersection is the vertices that we can use in our path, and if any vertex here is in a cycle, ans is -1

→ Ответить

hellstar

5 лет назад, скрыть # ^ |

Nodes that are not reachable from node 1 will always remain unchanged i.e INFINITY in the distance array. so only dfs from n'th node in reverse adj list is fine .

→ Ответить

Ashwanth.K

3 года назад, скрыть # ^ |

nice, then we can mark each node in 2 criteria
reachable_from_node_1_normal
reachable_from_node_n_reverse

If, after N iterations, both boolean values above are true, then the answer = -1.

→ Ответить

ankit1373

19 месяцев назад, скрыть # ^ |

If you run the bellman ford from 1, the you will never discover the negative cycles that are not reachable from 1, in the first place

→ Ответить

maxn1e5

5 лет назад, скрыть # |

← Rev. 2 →

2 1
1 2 -1

Answer is -1, but it isn't infinity score.

→ Ответить

bhavyakawatra

4 года назад, скрыть # |

← Rev. 3 →

idea

code

/*
    Author : Bhavya Kawatra
 Institute : MAIT
      Dept : CST
     Email : [email protected]
 CF handle : bhavyakawatra
*/
#include <bits/stdc++.h>
using namespace std;

//input full vector
template<class T>istream& operator >> (istream &is, vector<T>& V) {for(auto &e : V)is >> e;return is;}

#define db double
#define im INT_MAX
#define ll long long
#define mod 1000000007
#define mod2 998244353
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vp vector<pair<int,int>>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define T true
#define F false
#define mem(x, y) memset(x, y, sizeof(x))
#define sp(x) cout << fixed;cout << setprecision(x)
#define sz size()
#define mahadev ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define full_line(s) getline(cin, s)
#define in(n) int n;cin >> n
#define in2(a, b) int a,b;cin >> a >> b
#define in3(a, b, c) int a,b,c;cin >> a >> b >> c
#define in4(a, b, c,d) int a,b,c,d;cin >> a >> b >> c>>d
#define max_heap(pq) priority_queue <int> pq
#define min_heap(pq) priority_queue <int, vector<int>, greater<int> > pq
#define asort(v) sort(v.begin(),v.end())
#define dsort(v) sort(v.rbegin(),v.rend())
#define endl "\n"
#define pn(p) cout<<p<<endl
#define pt(p) cout<<p<<" "
#define pt2(p,q) cout<<p<<" "<<q<<endl
#define pt3(p,q,r) cout<<p<<" "<<q<<" "<<r<<endl
#define pt4(p,q,r,s) cout<<p<<" "<<q<<" "<<r<<" "<<s<<endl
#define vfor(v) for (auto itr =v.begin() ; itr!=v.end(); itr++)
#define vbfor(v) for (auto itr =v.rbegin() ; itr!=v.rend(); itr++)
#define ffor(i, a, b) for (int i = a; i < b; i++)
#define bfor(i, a, b) for (int i = a - 1; i >= b; i--)
#define all(v) v.begin(),v.end()
#define Y "YES" 
#define NO "NO" 
#define int long long
#define ai array<int,2>


/*------------------------------------begin------------------------------------

*/

vector<vector<ai>> g;
vi affected,accessedFromStart;

void dfs(int r){
    affected[r]=1;
    for(auto i:g[r]){
        if(!affected[i[0]]){
            dfs(i[0]);
        }
    }
}

void dfs1(int r){
    accessedFromStart[r]=1;
    for(auto i:g[r]){
        if(!accessedFromStart[i[0]]){
            dfs1(i[0]);
        }
    }
}

void solve()
{
    // declarations..
    in2(n,m);
    vi prnt(n+5,-1);
    vi dist(n+5,-1e15);
    affected.assign(n+5,0);
    vector<array<int,3>>edg;
    g.assign(n+5,vector<ai>());
    accessedFromStart.assign(n+5,0);

    // taking input
    ffor(i,0,m){
        in3(x,y,wt);
        edg.pb({x,y,wt});
        g[x].pb({y,wt});
    }

    // bellman ford algorithm..
    dist[1]=0;
    ffor(i,0,n-1){
        for(auto e:edg){
            if(dist[e[1]]<dist[e[0]]+e[2]){
                dist[e[1]]=dist[e[0]]+e[2];
                prnt[e[1]]=e[0];
            }
        }
    }

    // checking for positive weighted cycles (bellman ford)
    ffor(i,0,n){
        for(auto e:edg){
            if(dist[e[1]]<dist[e[0]]+e[2]){
                dist[e[1]]=dist[e[0]]+e[2];
                affected[e[1]]=1;// makrking nodes which are affected by cycles
            }
        }
    }

    dfs1(1); // to check node which can be accessed from start we are doing dfs1 ..
    // this is done because Starting Node is 1 (given)

    // checking which nodes are affected by cycle and are in path starting from 1
    ffor(i,1,n+1){
        if(accessedFromStart[i] && affected[i]){
            dfs(i);// chcking affected nodes can lead to which more nodes..
        }
    }

    // checking back path from n to 1 .. whether in between any node is affected by cylce 
    int r=n;
    while(r!=-1){
        if(affected[r]){
            pn(-1);
            return;
        }
        r=prnt[r];
    }
    pn(dist[n]);

}

/*-------------------------------------end-------------------------------------*/
signed main()
{
    // mahadev;
    solve();
    return 0;
}

→ Ответить

veshh

13 месяцев назад, скрыть # |

apply bellman ford with negative weights and then get the nodes which are affected in the nth loop. Put them in a queue and run bfs to get all the nodes affected by "affected" nodes. if the nth node is affected this means -1. otherwise print -1*distnceOfLastNode[i took negative weights].

→ Ответить