### Vedkribhu's blog

By Vedkribhu, history, 3 years ago,

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?

• 0

| Write comment?
 » 3 years ago, # |   +2 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.
•  » » 3 years ago, # ^ |   0 Can you please explain the intuition behind doing this?
•  » » » 3 years ago, # ^ |   0 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 71 2 12 7 11 6 -16 5 -15 4 -14 3 -13 1 5here, the +ve cycle affects the 'nth' node.But here,8 91 2 12 3 13 4 14 2 11 8 15 8 15 6 16 7 17 5 1it doesn't affect the nth node.
•  » » » 3 years ago, # ^ |   0 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).
•  » » » » 6 months ago, # ^ |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 what if the node (in the cycle and connected to n) is not connected to 1?1 4 12 4 12 3 13 2 1there'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 cyclewhat 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 connectedrun dfs from n in reversed graph, mark everyone connectedintersection is the vertices that we can use in our path, and if any vertex here is in a cycle, ans is -1
•  » » » 2 years ago, # ^ |   0 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 .
•  » » » 4 months ago, # ^ |   0 nice, then we can mark each node in 2 criteriareachable_from_node_1_normalreachable_from_node_n_reverse If, after N iterations, both boolean values above are true, then the answer = -1.
 » 2 years ago, # | ← Rev. 2 →   0 2 1 1 2 -1 Answer is -1, but it isn't infinity score.?
 » 8 months ago, # | ← Rev. 3 →   0 ideaidea : Apply bellman ford and analyze which all nodes are included in the cycleif any node that is included in cycle is reachable by 1 mark that node as affected or danger node.now backtrack from nth node to 1st node (starting node) .. if any danger node or affected node lies in this path then answer is -1. else return distance from 1 to n . code/* Author : Bhavya Kawatra Institute : MAIT Dept : CST Email : [email protected] CF handle : bhavyakawatra */ #include using namespace std; //input full vector templateistream& operator >> (istream &is, vector& 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 #define vb vector #define vvi vector #define vvb vector #define vp vector> #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 pq #define min_heap(pq) priority_queue , greater > pq #define asort(v) sort(v.begin(),v.end()) #define dsort(v) sort(v.rbegin(),v.rend()) #define endl "\n" #define pn(p) cout<= b; i--) #define all(v) v.begin(),v.end() #define Y "YES" #define NO "NO" #define int long long #define ai array /*------------------------------------begin------------------------------------ */ vector> 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>edg; g.assign(n+5,vector()); 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]]
 » 3 months ago, # |   0 using bellman ford, mark all the nodes which are part of negative cycle among the nodes marked in step 1, filter in those which are reachable through node 1 now ,among the filtered nodes obtained from step 2, count such nodes from which node n is reachable if the count obtained is greater than 0, that means ans is -1 else answer is (-1*distance[n]) (-1 we multiplied because we negated all weights in starting, so that we can find negative cycle instead of positive cycle) (Don't worry about Time complexity O(N^2) solution will easily pass)
 » 2 months ago, # |   0 uncomment the commented lines to understand the code. #include #define LL long long #define II pair #define PLL pair #define VI vector #define VVI vector #define VLL vector #define VII vector #define VVLL vector #define VVII vector> #define VPLL vector> #define VS vector #define VB vector #define VVB vector #define MMS0(a) memset(a,0,sizeof(a)) #define MMS1(a) memset(a,-1,sizeof(a)) #define AR array #define PB push_back #define FF first #define SS second #define FOR(n) for(int i=0;i=a;i--) #define LOOP(i,a,n,c) for(int i=a;ia;i-=c) #define DEB1(a) cout<<#a<<" "<= n || j >= m) return false; return true; } VVI edges; VVI graph; VVII weightedGraph; VVLL matrix; void readEdges(int M,bool isWeighted) { FOR(M) { int u,v,weight = 0; cin>>u>>v; if(isWeighted) { cin>>weight; } edges.PB(VI{u,v,weight}); } } void readEdgesAndCreatGraph(int n,int m,bool isWeighted,bool isDirected) { if(isWeighted) { weightedGraph.assign(n + 1,VII{}); while(m--){ int u,v,w; cin>>u>>v>>w; weightedGraph[u].PB(MKP(v,w)); if(!isDirected) weightedGraph[v].PB(MKP(u,w)); } }else{ graph.assign(n + 1,VI{}); while(m--){ int u,v; cin>>u>>v; graph[u].PB(v); if(!isDirected) graph[v].PB(u); } } } void printGraph(int V, bool isWeighted) { cout<<"\n"; cout<<"***************** Printing Graph started: **********************\n"; LOOP(u,0,V + 1,1) { cout<>u>>v>>w; matrix[u][v] = min(w,matrix[u][v]); if(!isDirected) matrix[v][u] = min(w,matrix[v][u]); } } /* ************************* SOLUTION STARTS HERE **************************** Identified by : he asked me to caluculate maximum score from source to destinaion. (reverse of Disjistra algorithm. -> instead of min we are finding maximum). So This is : Dijistra based problem. Approach : 1. apply disjistra algorithm. 2. after this there will be 3 cases based on dist and tempDist vector. case 1: tempDist == dist --> dist[n] case 2: dist[n] == -INFITE --> -1 is the answer. case 3: tempDist != dist 1. create an adj. list. 2. mark the non simililar nodes from tempDist and dist. 3. find whether we can reach marked from souce. . if we can then again from that point try to find whether we can reach destination then is -1. */ bool DFS_canReachDestinationFromMarked(int u, int n,VB &visited) { if(u == n) return true; visited[u] = true; for(auto v:graph[u]) { if(!visited[v]) { if(DFS_canReachDestinationFromMarked(v,n,visited)) return true; } } return false; } bool DFS_canReachMarkedFromSource(int u,int n, VB &visited,VB &marked) { if(marked[u]) { VB visitedFromMarkedToDestination(n + 1,false); if(DFS_canReachDestinationFromMarked(u,n,visitedFromMarkedToDestination)) { // cout<<"------------------\n"; // LOOP(i , 1, n + 1, 1) cout<>n>>m; //readEdgesAndCreatGraph(n,m,true,true); readEdges(m,true); belmanFordAlgorithm(n,m); return 0; }