TheCreator's blog

By TheCreator, history, 2 months ago, In English

Given an undirected connected graph with N vertices and M edges, and a set S of K nodes of this graph.

Find the maximum number of edges that we can remove from the graph such that all these K nodes still remains connected (i.e there exist one component which has all these K nodes )

eg -: edges -:[[1 2], [1 3],[2 4],[3 4]] S = [1, 2, 4]

We can remove maximum of 3 edges [1, 3] and [3, 4] and [1, 4], removing any other edges makes given set of nodes disconnected.

How to solve this ?

I can only think of trying all 2^m subset of edges.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By TheCreator, history, 3 months ago, In English

Given a connected undirected graph consisting of N N nodes, determine how many connected components the graph will break into if each node is removed.

For example, consider a graph with the following undirected edges:

1-2, 1-3, 1-4, 4-5, 5-6, 4-6.

If we remove node 1, there will be 3 connected components. If we remove node 2, there will be 1 connected component. If we remove node 3, there will be 1 connected component. If we remove node 4, there will be 2 connected components. If we remove node 5, there will be 1 connected component. If we remove node 6, there will be 1 connected component.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By TheCreator, history, 5 years ago, In English

Given two integer array of size $$$n$$$, $$$m$$$, you need to merge these two arrays into one such that order of element in each array doesn't change and size of their Longest Increasing Subsequence become maximum.

we need to find maximum possible length of longest increasing subsequence. Assume $$$n, m < 100$$$.

Full text and comments »

Tags #dp
  • Vote: I like it
  • +8
  • Vote: I do not like it