How do I select maximum vertices in a graph in this case:-?

Блог пользователя umsh1ume

Автор umsh1ume, история, 7 лет назад, По-английски

I need to select maximum vertices in a graph such that the distance between any two selected vertices is less than the given limit? distance between adjacent nodes is 1. Input n,d meaning number of nodes and the limit d, n-1 lines follows denoting edges. Example 6 5 2 1 2 3 4 2 1 6 5 6

Output 5 As all 5 vertices can be selected within the range d

-6

umsh1ume
7 лет назад
7

Комментарии (7)

Написать комментарий?

xsc

7 лет назад, # |

-6

Seems, your graph is a tree, because you wrote there n-1 edges. If so, there exists simple algo O(n^2), for every node run BFS no longer distance than d. calculate number of nodes.

source

typedef vector<int> vi;
int const N = 1000;
vi G[N];
int n, d;
void read(){  
cin >> n >> d; 
for (int i= 0; i<n-1;++i){ 
int a,b; 
cin >> a >> b; G[a].push_back(b);
G[b].push_back(a); }
} // end read

int bfs(int root)
{
    queue<int> q;
    q.push(root);
    vi dist(n+1, INT_MAX);
    dist[root] = 0;
    while(!q.empty()) {
         int u = q.front(); q.pop();
          
          for(size_t i = 0; i < G[u].size(); ++i)
          {
               int to = G[u][i]; 
               if ( dist[to] == INT_MAX && 1 + dist[u] <= d )
               {
                    dist[to] = 1 + dist[u]; q.push(to);
                }
          }
    }

    int ans = 0; for(int i = 1; i<=n; ++i) if (dist[i]  <= d ) ++ans;
    return ans;
}

int main(){
    read();
    int ans = 0;
    for(int root = 1; root <= n; ++root) ans = max(ans, bfs(root));
    cout << ans << endl;
}

And, I belive that, there must exists linear solution.

→ Ответить

repeating

7 лет назад, # ^ |

3 1

1 2

2 3

in this case your output is 3 but the answer is 2

→ Ответить

xsc

7 лет назад, # ^ |

← Rev. 2 →

Thanks, yea, I didn't read problem carefully.

There required distance for each vertex in the set must less than limit d.

→ Ответить

repeating

7 лет назад, # |

if n<=20 , then you can solve it by dp + bitmask

→ Ответить

xsc

7 лет назад, # |

CAN YOU SHARE LINK TO PROBLEM ?

→ Ответить

xsc

7 лет назад, # |

← Rev. 2 →

If this graph is a tree, there exists O(N^2) solution.

In the graph for every pair of vertexes exist single path.

Think that, if we build solution, there exist a pair of vertexes where distance is maximum, select middle of these vertexes, for selected vertex, distance from it to any other vertexes in the set less or equal (1+d)/2.

→ Ответить

___---___

7 лет назад, # |

dp[i][j][k] -- number of nodes in subtree rooted at node i , using jth of its child , upto a depth of of k.. For every node , we will have the number of nodes in each child subtree upto different heights of different nodes..

→ Ответить