### Find the right root

Hello everyone, may I ask that given size, nodes and edges of a tree. How can I find the correct node to be the root so that the maximal number of nodes in subtree is minimal among all.
For example:

Input :

6 (size of tree)
0 1 (connected nodes)
1 2 (connected nodes)
1 3 (connected nodes)
3 4 (connected nodes)
3 5 (connected nodes)

Output :
1
3
This is the closet that I can get. Thanks a lot for anyone's help.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778`` `````` #include using namespace std; vector> graph; // Function to perform the DFS calculating the // count of the elements in a connected component void dfs(int curr, int& cnt, vector& visited, vector& duringdfs) { visited[curr] = 1; // Number of nodes in this component ++cnt; // Stores the nodes which belong // to current component duringdfs.push_back(curr); for (auto& child : graph[curr]) { // If the child is not visited if (visited[child] == 0) { dfs(child, cnt, visited, duringdfs); } } } // return the desired count for every node in the graph void MaximumVisit(int n, int k) { // To keep track of nodes visit vector visited(n+1,0); // No of connected elements for each node vector ans(n+1); vector duringdfs; for (int i = 1; i <= n; ++i) { duringdfs.clear(); int cnt = 0; // If a node is not visited, perform a DFS as // this node belongs to a different component // which is not yet visited if (visited[i] == 0) { cnt = 0; dfs(i, cnt, visited, duringdfs); } // store the count of all the visited // nodes for any particular component. for (auto& x : duringdfs) { ans[x] = cnt; } } for (int i = 1; i <= n; ++i) { cout << ans[i] << " "; } cout << endl; return; } void MakeGraph(int a, int b) { graph[a].push_back(b); } int main() { int n,a,b; cin>>n; graph.resize(n+1); MaximumVisit(n, n-1); while(n--) {cin>>a>>b; MakeGraph(a,b);} return 0; }``````
Last edited on
I presume you are taking an algorithms course. Assignments like these are to get you to try to recognize an appropriate algorithm for solving the given problem, and then to implement that algorithm yourself.

What algorithms have you been studying? Can you find one that is more useful than a DFS? (You can.)

I am aware that it is possible that your instructions were to use a DFS. Let us know if I was off base there.
Last edited on
Hi,yes you're right. We've been learning DFS so that's why I tried to use it, while the assignments didn't specify the methods as long as it works.
One way of doing it is to construct a table
d[i][j]
containing the minimum distance from i to j.

Then find the maximum value in each row (say): D[i]. This is the longest outward path from a root at i.

Then find the collection of i values with the minimum D[i].

Of course, constructing that table d[i][j] could be more or less long-winded ... !

Last edited on
I would say that since you are studying DFS that is probably the right tack to take.
Noted, thank you, is it possible to explain it more in detail?
Last edited on
You have the right idea.

For each node in the graph, perform a DFS and remember the distance to the furthest node.
Each time through the loop remember the currently minimal node+distance pair. (Just like a find the minimum loop kind of homework.)

Hello, still failed upon this attempt. I got incorrect answer.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667`` ``````#include using namespace std; vector dist; vector vis; void dfs(int u, vector Adj[], int s) { vis[u] = true; for (auto& it : Adj[u]) { if (vis[it] == false) { dfs(it, Adj, s + 1); } } dist[u] = max(dist[u], s); } void minFarthestDistance(int arr[][2], int n) { // Resize distance vector dist.resize(n + 1, 0); // To create adjacency list for graph vector Adj[n + 1]; // Create Adjacency list for every // edge given in arr[][] for (int i = 0; i < n - 1; i++) { Adj[arr[i][0]].push_back(arr[i][1]); Adj[arr[i][1]].push_back(arr[i][0]); } // DFS Traversal for every node in the // graph to update the distance vector for (int i = 1; i <= n; i++) { // Clear and resize vis[] before // DFS traversal for every vertex vis.clear(); vis.resize(n + 1, false); // DFS Traversal for vertex i dfs(i, Adj, 0); } cout << *min_element(dist.begin() + 1, dist.end()); } int main() { int N,a,b ; cin>>N; int arr[N][2]; N--; for(int i=0;i>a>>b; arr[a][2]=b;} minFarthestDistance(arr, N); return 0; } ``````
Last edited on

Do you require:
(1) the DEPTH of the subtrees?
or
(2) the COUNT of nodes in the PROPER subtrees (i.e. excluding the node itself)?

Both give the same answer for the sample problem - so that isn't helpful.

Programs below to solve each.

Program (1): Minimise over maximum DEPTHS of subtrees

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243`` ``````#include #include #include using namespace std; //========================================================== int getDepth( int i, int parent, const vector< vector > &graph ) { int mx = 0; for ( int j : graph[i] ) { if ( j != parent ) mx = max( mx, getDepth( j, i, graph ) ); } return 1 + mx; } //========================================================== int main() { istringstream in(); int n; cin >> n; vector< vector > graph( n ); // Connectors for each node for ( int i = 1; i < n; i++ ) // Tree has n-1 edges { int a, b; cin >> a >> b; graph[a].push_back( b ); graph[b].push_back( a ); } // For each node, find depth of tree with that node as root vector depth( n ); for ( int i = 0; i < n; i++ ) depth[i] = getDepth( i, -1, graph ); // Minimise depth (==> "centre" of tree) int minimum = *min_element( depth.begin(), depth.end() ); for ( int i = 0; i < n; i++ ) if ( depth[i] == minimum ) cout << i << ' '; cout << '\n'; }``````

Program (2): Minimise over maximal COUNTS of PROPER subtrees

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647`` ``````#include #include #include using namespace std; //========================================================== int subtreeSize( int i, int parent, const vector< vector > &graph ) { int sum = 1; for ( int j : graph[i] ) { if ( j != parent ) sum += subtreeSize( j, i, graph ); } return sum; } //========================================================== int main() { istringstream in(); int n; cin >> n; vector< vector > graph( n ); // Connectors for each node for ( int i = 1; i < n; i++ ) // Tree has n-1 edges { int a, b; cin >> a >> b; graph[a].push_back( b ); graph[b].push_back( a ); } // For each node, find maximal count amongst its proper subtrees vector subcount( n, 0 ); for ( int i = 0; i < n; i++ ) { for ( int j : graph[i] ) subcount[i] = max( subcount[i], subtreeSize( j, i, graph ) ); } // Minimise subtree count int minimum = *min_element( subcount.begin(), subcount.end() ); for ( int i = 0; i < n; i++ ) if ( subcount[i] == minimum ) cout << i << ' '; cout << '\n'; }``````

Last edited on
Hello! I believe it should be the count of sub trees excluding the parent node. However, Is there a way to improve the time complexity of program 2 ?
Last edited on
Tell me what the outcome for program 2 is.

Does it fail with wrong answers or just timeout? There is no point in trying to improve complexity (which I could probably do just by memoisation) if the answers are wrong or the problem is misunderstood.

Please show either a link or a picture of the original problem, not your paraphrasing of it.
Here's a memoised version of program 2.

If n is large then it will have VERY large space requirements. If that is a problem then you will have to change memo from a vector<vector<int>>(n,n) to a map<pair<int,int>,int>

How large can n get?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051`` ``````#include #include #include using namespace std; //========================================================== int subtreeSize( int i, int parent, const vector< vector > &graph, vector< vector > &memo ) { if ( parent >= 0 && memo[i][parent] > 0 ) return memo[i][parent]; // Computed before, so no need to recurse int sum = 1; for ( int j : graph[i] ) { if ( j != parent ) sum += subtreeSize( j, i, graph, memo ); } memo[i][parent] = sum; // Store value in case needed again return sum; } //========================================================== int main() { istringstream in(); int n; cin >> n; vector< vector > graph( n ); // Connectors for each node for ( int i = 1; i < n; i++ ) // Tree has n-1 edges { int a, b; cin >> a >> b; graph[a].push_back( b ); graph[b].push_back( a ); } // For each node, find maximal count amongst its proper subtrees vector subcount( n, 0 ); vector< vector > memo( n, vector( n, 0 ) ); // This could be very expensive for large n! for ( int i = 0; i < n; i++ ) { for ( int j : graph[i] ) subcount[i] = max( subcount[i], subtreeSize( j, i, graph, memo ) ); } // Minimise subtree count int minimum = *min_element( subcount.begin(), subcount.end() ); for ( int i = 0; i < n; i++ ) if ( subcount[i] == minimum ) cout << i << ' '; cout << '\n'; }``````

And here's a version of program of Program 2 that uses a map for the memoisation (much smaller space requirements, but slightly slower in time).

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657`` ``````#include #include #include #include #include using namespace std; //========================================================== int subtreeSize( int i, int parent, const vector< vector > &graph, map,int> &memo ) { if ( parent >= 0 ) { auto it = memo.find( {i,parent} ); if ( it != memo.end() ) return it->second; // Computed before, so no need to recurse } int sum = 1; for ( int j : graph[i] ) { if ( j != parent ) sum += subtreeSize( j, i, graph, memo ); // Recurse through children } memo[{i,parent}] = sum; // Store value in case needed again return sum; } //========================================================== int main() { istringstream in(); int n; cin >> n; vector< vector > graph( n ); // Connectors for each node for ( int i = 1; i < n; i++ ) // Tree has n-1 edges { int a, b; cin >> a >> b; graph[a].push_back( b ); graph[b].push_back( a ); } // For each node, find maximal count amongst its proper subtrees vector subcount( n, 0 ); map,int> memo; // Allow for memoisation for ( int i = 0; i < n; i++ ) { for ( int j : graph[i] ) subcount[i] = max( subcount[i], subtreeSize( j, i, graph, memo ) ); } // Minimise subtree count int minimum = *min_element( subcount.begin(), subcount.end() ); for ( int i = 0; i < n; i++ ) if ( subcount[i] == minimum ) cout << i << ' '; cout << '\n'; }``````

Greetings, thank you for your help, solved now.