Find the right root

[satsat111]

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
(cuz there's two best answers)
This is the closet that I can get. Thanks a lot for anyone's help.

 #include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
 
// Function to perform the DFS calculating the
// count of the elements in a connected component
void dfs(int curr, int& cnt, vector<int>& 
             visited, vector<int>& 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<int> visited(n+1,0);
   
      // No of connected elements for each node  
      vector<int> ans(n+1);
 
    vector<int> 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;
}

[Duthomhas]

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.)


[edit]
I am aware that it is possible that your instructions were to use a DFS. Let us know if I was off base there.

[satsat111]

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.

[lastchance]

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 ... !

[Duthomhas]

I would say that since you are studying DFS that is probably the right tack to take.

[satsat111]

Noted, thank you, is it possible to explain it more in detail?

[Duthomhas]

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.)

[satsat111]

Hello, still failed upon this attempt. I got incorrect answer.

#include <bits/stdc++.h>
using namespace std;
 
vector<int> dist;
vector<int> vis;
void dfs(int u, vector<int> 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<int> 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<N;i++)
    {cin>>a>>b;
     arr[a][2]=b;}
 
    minFarthestDistance(arr, N);
    return 0;
}
 

[lastchance]

Your question is AMBIGUOUS.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int getDepth( int i, int parent, const vector< vector<int> > &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<int> > 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<int> 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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int subtreeSize( int i, int parent, const vector< vector<int> > &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<int> > 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<int> 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';

}

[satsat111]

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 ?

[lastchance]

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.

[satsat111]

There's five correct answers and two time-limit exceeded, no wrong answer.

[lastchance]

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?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int subtreeSize( int i, int parent, const vector< vector<int> > &graph, vector< vector<int> > &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<int> > 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<int> subcount( n, 0 );
   vector< vector<int> > memo( n, vector<int>( 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';
}

[lastchance]

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).

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>
using namespace std;

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

int subtreeSize( int i, int parent, const vector< vector<int> > &graph, map<pair<int,int>,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<int> > 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<int> subcount( n, 0 );
   map<pair<int,int>,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';
}

[satsat111]

Greetings, thank you for your help, solved now.