CareerCup

Can be solved by taking the max flow where A is the source and B the desination. The min number of edges to remove would be the flow. (max flow, min cut)

Finding shortest path will not help. We need to remove all possible paths.

Can someone clarify this question. We can directly disconnect two nodes by removing the edge connecting them. I know this is not the answer please elaborate this question.

I think that this is a Edmonds-Karp based solution, but i dont know how to implement it :(

int bfs(int graph[][V],int src,int dest,int parent[])
{
    int visited[V];
    int i=0;
    for(i=0;i<V;i++)
       visited[i]=0;
    push(src);
    parent[src]=-1;
    visited[src]=1;
    int temp = pop();
    while(temp!=-1)
    {
        for(i=0;i<V;i++)
        {
           if(visited[i]==0 && graph[temp][i]>0)
           {
              visited[i]=1;
              push(i);
              parent[i]=temp;
           }
        }
        temp=pop();
    }
    return visited[dest];
}

void dfs(int graph[][V],int src,int visited[])
{
     visited[src]=1;
     int i=0;
     for(i=0;i<V;i++)
     {
        if(visited[i]==0 && graph[src][i]>0)
           dfs(graph,i,visited);
     }
}

int getmin(int graph[][V],int src,int dest)
{
    int res[V][V];
    int i=0,j=0;
    for(j=0;j<V;j++)
    {
       for(i=0;i<V;i++)
          res[i][j] = graph[i][j];
    }
    int parent[V];
    int flow=1000;
    int mincap=0;
    while(bfs(res,src,dest,parent))
    {
        flow = 1000;
        int v = dest;
        while(v!=src)
        {
           int u = parent[v];
           if(flow>res[u][v])
              flow = res[u][v];
           v=u;
        }
        v = dest;
        while(v!=src)
        {
           int u = parent[v];
           res[u][v] = res[u][v]-flow;
           res[v][u] = res[v][u]+flow;
           v = u;
        }
        mincap = mincap + flow;
    }
    int visited[V];
    for(i=0;i<V;i++)
       visited[i]=0;
    dfs(res,src,visited);
    for(i=0;i<V;i++)
    {
       for(j=0;j<V;j++)
       {
           if(visited[i]==1 && visited[j]==0 && graph[i][j]>0)
              printf("%d---->%d\t",i,j);
       }
    }
    printf("\n");
    return mincap;
}

Direction is to find all possible paths, and remove most common edges.
If space is not a problem, solution should maintain each edge's occurrence count, and reference to paths on which it occurs.

Algorithm should remove edge with highest occurrence count, then discard paths, on which it was occurring.
Repeat the same process, until all paths are discarded.

If the graph is directed-
1) Add a dummy source to the first node with capacity infinity.
2) Add a dummy sink to the second node with capacity infinity.
3) Give all other nodes capacity 1.
4) Apply ford-fulkerson algorithm, max-flow value will give the minimum number of edges to disconnect the two nodes.Because max-flow is equal to min-cut.

If the graph is undirected.
1) Reduce it to the directed graph.
2) Apply the same procedure as stated above.

1. Find all possible paths
2. Go through the path set, find the smallest sub edge set in common

2 Could be done by ranking the edges and use dynamic planning to figure out the minimal edge set that covers all paths.

The quesiton asked us to find an Articulation Edge (Bridge) in disguise and DFS can be used to find such and Edge Complexity O(V+E).

Do DFS to get all the paths from node1 to node2. Build set of edges for each path. Now this is the famous set cover problem - find the minimum edges covering all paths and remove them.

This is classified DP problem

I think we can transfer the question as to search for the shortest path between A and B with treating all edge weights equal to 1, then we can solve the question with Dijkstra's algorithm.