JUSPAY || SDE Intern + PPO || Maximum Weight Node || Largest Sum Cycle || Nearest Meeting Cell
There was total 3 problems based on Graph. All 3 problems had same statement but different tasks to perform.
This was the common statement.
Given a maze with N cells. Each cell may have multiple entry points but not more than one exit (i.e entry/exit points are unidirectional doors like valves).
You are given an array Edge[] of N integers, where Edge[i] contains the cell index that can be reached from cell i in one step. Edge[i] is -1 if the ith cell doesn't have an exit.
Problem : 1 Maximum Weight Node (Easy)
The task is to find the cell with maximum weight (The weight of a cell is the sum of cell indexes of all cells pointing to that cell). If there are multiple cells with the maximum weight return the cell with highest index.
Note: The cells are indexed with an integer value from 0 to N-1. If there is no cell pointing to the ith cell then the weight of the i'th cell is zero.
INPUT FORMAT :
The first line contains the number of cells N.
The second line has a list of N values of the edge[ ] array, where edge[i] conatins the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the ith doesn't have ans exit.
OUTPUT FORMAT :
First line denotes the node number with maximum weight node.
Sample Input :
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
Sample Output :
22
int maxWeightCell(int n, vector<int> edge){
vector<int> cnt(n,0);
for(int i=0; i<n; i++){
if(edge[i] != -1)
cnt[edge[i]] += i;
}
int ans = -1;
int maxi = INT_MIN;
for(int i=0; i<n; i++){
if(maxi <= cnt[i]){
maxi = cnt[i];
ans = i;
}
}
return ans;
}Problem : 2 Largest Sum Cycle (Medium-Hard)
The task is to find the largest sum of a cycle in the maze(Sum of a cycle is the sum of the cell indexes of all cells present in that cycle).
Note:The cells are named with an integer value from 0 to N-1. If there is no cycle in the graph then return -1.
Example 1:
Input:
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
Output:
45
Example 2:
Input:
N = 4
Edge[] = {2, 0, -1, 2}
Output:
-1
Explanation:
1 -> 0 -> 2 <- 3
There is no cycle in the graph.
long long largestSumCycle(int n, vector<int> edge)
{
// cnt vector will count the Indegree of each Node
vector<int> cnt(n,0);
for(auto i : edge){
if(i != -1) cnt[i]++;
}
queue<int> q;
/*
Fact that a Node with indegree = 0 is out of cycle.
We'll mark that node visited and cut that node from the graph.
To do so, find the edge from that node and decrease the indegree of edge[node] by 1.
*/
vector<int> vis(n,0);
for(int i = 0; i<n; i++){
if(cnt[i]==0){
vis[i] = 1;
q.push(i);
}
}
while(!q.empty()){
int node = q.front(); q.pop();
if(edge[node] == -1) continue;
--cnt[edge[node]];
if(cnt[edge[node]] == 0){
vis[edge[node]] = 1;
q.push(edge[node]);
}
}
int ans = -1;
for(int i = 0; i<n; i++){
if(vis[i]) continue;
int val = 0;
for(int st = i; vis[st] == 0; st = edge[st]){
vis[st] = 1;
val += st;
}
ans = max(ans,val);
}
return ans;
}Problem : 3 Nearest Meeting Cell (Hard)
The task is to find :- Nearest meeting cell : Given any two cells - C1, C2, find the closest cell Cm that can be reached from both C1 and C2.
Note:- The cells are named with an integer value from 0 to N-1. If there is no node pointing to the ith node then weight of the ith node is zero.
INPUT FORMAT :-
The first line contains the number of cells N.
The second line has a list of N values of the edge[ ] array, where edge[i] conatins the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the ith doesn't have an exit.
Third line for each testcase contains two cell numbers whose nearest meeting cell needs to be found. (return -1 if there is no meeting cell.
OUTPUT FORMAT :
Output a single line that denotes the nearest meeting cell (NMC).
Sample Input :
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
9 2
Sample Output :
4
#include <bits/stdc++.h>
using namespace std;
#define INF INT_MAX
vector<long long> Dijkstra(vector<vector<int>>& adj, int s)
{
priority_queue<pair<long, long>, vector<pair<long, long>>, greater<pair<long, long>>> pq;
int v = adj.size();
vector<long long> ans(v, INF);
ans[s] = 0;
pq.push({0, s});
while (!pq.empty())
{
long long dist = pq.top().first;
int node = pq.top().second;
pq.pop();
for (auto i : adj[node])
{
if (dist + 1 < ans[i])
{
ans[i] = dist + 1;
pq.push({dist + 1, i});
}
}
}
return ans;
}
int minimumWeight(int n, vector<int>& edges, int C1, int C2)
{
vector<vector<int>> graph(n);
for (int i = 0; i < n; i++)
{
if (edges[i] != -1)
graph[i].push_back(edges[i]);
}
// Create two arrays A and B for storing min distance from C1 and C2
vector<long long> A(n, INF), B(n, INF);
// Part 1 and Part 2 of Algo -> Implement a Dijkstra function and call it for both arrays A and B
A = Dijkstra(graph, C1);
B = Dijkstra(graph, C2);
// Now comes Part 3 part of algo-> loop through and get node with min(A[i]+B[i])
int node = -1;
long long dist = INF;
for (int i = 0; i < n; ++i)
{
// If node is not accessible from any of them, ignore it
if (A[i] == INF || B[i] == INF)
continue;
if (dist > A[i] + B[i])
{
dist = A[i] + B[i];
node = i;
}
}
return node;
}
int main()
{
int n;
cin >> n;
vector<int> edges(n);
for (int i = 0; i < n; ++i)
{
cin >> edges[i];
}
int C1, C2;
cin >> C1 >> C2;
int nearestMeetingCell = minimumWeight(n, edges, C1, C2);
cout << nearestMeetingCell << endl;
return 0;
}
**Note: Problem 1 and 2 is gfg problems and 3rd one is kind of variation.
