### Weighted graph

Hello everyone, I got problem putting the weights of each child's and getting the max weighted child among them in the code. Some said that this should be solved first through strongly connected components then perform the DFS, but that seems so complicated, thanks for any help.

Here is a Directed Acyclic Graph (DAG) with weight on nodes.
If there is a directed path from node a to node b, node b is a successor of node a.a itself is defined as one of the successors of a as well.
Calculate the maximal weight among weights of all successors of v for each v in the DAG.

Input Format
The first line is n,m which are number of nodes and directed edges in the DAG.
The following n line are n integers representing weight of node i,0<=i<n .
The following m line after weights are m pair of integers, (a,b), which represents directed edge from a to b.

Output Format
Print n integers in a line separate with a space.
The i-th integer is the answer corresponding to node i, 0<=i<n .

Sample Input
5 5
1 4 3 2 8
0 1
1 2
1 3
3 2
0 4

Sample Output

8 4 3 3 8

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142`` ``````#include #include #include #include #include #include using namespace std; class Graph { public: int V; // No. of vertices // Pointer to an array containing adjacency lists list *adj; Graph(int ); // Constructor void addEdge(int, int); vector BFS(int, int, int []); }; Graph::Graph(int V) { this->V = V; adj = new list[V+1]; } void Graph::addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } vector Graph::BFS(int componentNum, int src, int visited[]) { // Mark all the vertices as not visited // Create a queue for BFS queue queue; queue.push(src); visited[src] = componentNum; vector reachableNodes; while(!queue.empty()) { int u = queue.front(); queue.pop(); reachableNodes.push_back(u); // Get all adjacent vertices of the dequeued // vertex u. If a adjacent has not been visited, // then mark it visited and enqueue it for (auto itr = adj[u].begin(); itr != adj[u].end(); itr++) { if (!visited[*itr]) { // Assign Component Number to all the // reachable nodes visited[*itr] = componentNum; queue.push(*itr); } } } return reachableNodes; } void displayReachableNodes(int n, unordered_map > m) { vector temp = m[n]; for (int i=0; i > m; // Initialize component Number with 0 int componentNum = 0; // For each node in arr[] find reachable // Nodes for (int i = 0 ; i < n ; i++) { int u = arr[i]; // Visit all the nodes of the component if (!visited[u]) { componentNum++; // Store the reachable Nodes corresponding to // the node 'i' m[visited[u]] = g.BFS(componentNum, u, visited); } displayReachableNodes(visited[u], m); } } int main() { int n,m; cin>>n>>m; Graph g(n); int arr[n]; for(int i=0;i>i;} while(m--) { int u,v; cin>>u>>v; g.addEdge(u, v); } findReachableNodes(g, arr, n); return 0; } ``````

Last edited on
 ``1234567891011121314151617181920212223242526272829303132333435363738394041`` ``````#include #include #include using namespace std; //========================================================== int findMaxWeight( const vector< vector > &graph, const vector &weight, vector &maxWeight, int i ) { if ( maxWeight[i] >= 0 ) return maxWeight[i]; // Already dealt with int result = weight[i]; for ( int j : graph[i] ) result = max( result, findMaxWeight( graph, weight, maxWeight, j ) ); maxWeight[i] = result; return result; } //========================================================== int main() { istringstream in(); int n, m; cin >> n >> m; vector< vector > graph( n ); // Collection of direct successors for each node vector weight( n ); // Weights vector maxWeight( n, -1 ); // Maximum weight of node or successors (-1 implies unvisited) for ( int i = 0; i < n; i++ ) cin >> weight[i]; for ( int i = 0; i < m; i++ ) { int a, b; cin >> a >> b; graph[a].push_back( b ); // One-way relationship (directed graph) } for ( int i = 0; i < n; i++ ) findMaxWeight( graph, weight, maxWeight, i ); for ( int i = 0; i < n; i++ ) cout << maxWeight[i] << ' '; cout << '\n'; }``````

Last edited on
Hello, thanks for the kind reply, updated another version here https://ask.csdn.net/questions/7716600, and yes, problem solved.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142`` ``````#include #include #include #include using namespace std; struct Node { int weight; std::vector successors; }; int main() { int n, m; cin >> n >> m; std::vector nodes; nodes.resize(n); for (int i = 0; i < n; ++i) { int w; cin >> w; nodes[i].weight = w; } for (int i = 0; i < m; ++i) { int l, r; cin >> l >> r; nodes[l].successors.push_back(r); } for (int i = 0; i < n; ++i) { int maxWeight = nodes[i].weight; for (int j = 0; j < nodes[i].successors.size(); ++j) { if (maxWeight < nodes[nodes[i].successors[j]].weight) { maxWeight = nodes[nodes[i].successors[j]].weight; } } cout << maxWeight; if (i != n - 1)cout << " "; } return 0; }``````
Last edited on
"Your" solution appears to have been lifted from here:
https://ask.csdn.net/questions/7716600

Maybe you should give them credit.
Last edited on
Hello, actually I discussed with my friend and a friend of mine gave me this, I didn't know that it came from here.
Registered users can post here. Sign in or register to post.