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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

class Graph
{
public:
    int V;    // No. of vertices
 
    // Pointer to an array containing adjacency lists
    list<int> *adj;
 
    Graph(int );  // Constructor
 
    void addEdge(int, int);
 
    vector<int> BFS(int, int, int []);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V+1];
}
 
void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v); 
    adj[v].push_back(u); 
}
 
vector<int> Graph::BFS(int componentNum, int src,
                                    int visited[])
{
    // Mark all the vertices as not visited
    // Create a queue for BFS
    queue<int> queue;
 
    queue.push(src);
 
    visited[src] = componentNum;
    vector<int> 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 <int, vector<int> > m)
{
    vector<int> temp = m[n];
    for (int i=0; i<temp.size(); i++)
        cout << temp[i] << " ";
 
    cout << endl;
}
 

void findReachableNodes(Graph g, int arr[], int n)
{
    
    int V = g.V;
 
    // Take a integer visited array and initialize
    // all the elements with 0
    int visited[V+1];
    memset(visited, 0, sizeof(visited));
 
    // Map to store list of reachable Nodes for a
    // given node.
    unordered_map <int, vector<int> > 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<n;i++) arr[i]=i;
    while(n--)
    {int i; cin>>i;}
    while(m--)
    {
       int u,v;
        cin>>u>>v;
        g.addEdge(u, v);     
    }
    findReachableNodes(g, arr, n);
    return 0;
}


Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//==========================================================

int findMaxWeight( const vector< vector<int> > &graph, const vector<int> &weight, vector<int> &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<int> > graph( n );        // Collection of direct successors for each node
   vector<int> weight( n );                 // Weights
   vector<int> 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio> 
#include <vector> 
#include <iostream>
#include <algorithm> 
using namespace std;
struct Node
{
    int weight;
    std::vector<int> successors;
};
int main() {
    int n, m;
    cin >> n >> m;
    std::vector<Node> 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.