HackerRank Crab Graphs problem solution

In this HackerRank Crab Graphs problem solution, A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1 <= K <= T, where T is given)

Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.

Note: two graphs are vertex-disjoint if they do not have any vertices in common. 

Input Format

The first line of input contains a single integer C. C test-cases follow. The first line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated values v1i, v2i meaning that the there is an edge between vertices v1i and v2i. Note that the graph doesn’t have parallel edges or loops.

HackerRank Crab Graphs problem solution in Python.

from math import inf
import queue
def bfs(G, parent, s, t):
    n = len(G)
    visited = [False for _ in range(n)]
    q = queue.Queue(maxsize=0)
    q.put(s)
    visited[s] = True
    while not q.empty():
        curr = q.get()
        for v, val in enumerate(G[curr]):
            if not visited[v] and val > 0:
                q.put(v)
                visited[v] = True
                parent[v] = curr
    return visited[t]


def maxFlow(G, s, t):
    n = len(G)
    parent = [None for _ in range(n)]
    max_flow = 0
    while bfs(G, parent, s, t):
        path_flow = inf
        v = t
        while v != s:
            path_flow = min(path_flow, G[parent[v]][v])
            v = parent[v]
        max_flow += path_flow
        v = t
        while v != s:
            u = parent[v]
            G[u][v] -= path_flow
            G[v][u] += path_flow
            v = parent[v]
    return max_flow


def crabGraphs(n, T, graph):
    G = [[0 for _ in range(2*n + 2)] for _ in range(2*n+2)]
    for u, v in graph:
        G[u-1][n+v-1] = 1
        G[v-1][n+u-1] = 1
    s = 2*n
    t = 2*n + 1
    for u in range(n):
        G[s][u] = min(T, sum(G[u]))
        G[n+u][t] = 1
    return maxFlow(G, s, t)

if __name__ == '__main__':
    c = int(input().strip())

    for c_itr in range(c):
        first_multiple_input = input().rstrip().split()

        n = int(first_multiple_input[0])

        t = int(first_multiple_input[1])

        m = int(first_multiple_input[2])

        graph = []

        for _ in range(m):
            graph.append(list(map(int, input().rstrip().split())))

        result = crabGraphs(n, t, graph)
        print(result)

Crab Graphs problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the crabGraphs function below.
     */
    static int crabGraphs(int n, int t, int[][] graph) {
        List<Set<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacency.add(new HashSet<>());
        }
        for (int[] edge : graph) {
            int n1 = edge[0] - 1;
            int n2 = edge[1] - 1;
            adjacency.get(n1).add(n2);
            adjacency.get(n2).add(n1);
        }

        Deque<Integer> leaves = new ArrayDeque<>();
        int cover = n;
        for (int i = 0; i < n; i++) {
            if (adjacency.get(i).isEmpty()) {
                cover--;
            } else if (adjacency.get(i).size() == 1) {
                leaves.addLast(i);
            }
        }

        int[] legs = new int[n];
        while (!leaves.isEmpty()) {
            int leaf = leaves.removeFirst();
            if (legs[leaf] > 0) {
                continue;
            }

            if (adjacency.get(leaf).isEmpty()) {
                cover--;
            } else {
                int head = adjacency.get(leaf).stream().findAny().get();
                legs[head]++;
                if (legs[head] == t) {
                    for (int neighbor : adjacency.get(head)) {
                        adjacency.get(neighbor).remove(head);
                        if (adjacency.get(neighbor).size() == 1) {
                            leaves.addLast(neighbor);
                        }
                    }
                }
            }
        }
        return cover;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int c = scanner.nextInt();
        scanner.skip("(rn|[nru2028u2029u0085])*");

        for (int cItr = 0; cItr < c; cItr++) {
            String[] ntm = scanner.nextLine().split(" ");
            scanner.skip("(rn|[nru2028u2029u0085])*");

            int n = Integer.parseInt(ntm[0]);

            int t = Integer.parseInt(ntm[1]);

            int m = Integer.parseInt(ntm[2]);

            int[][] graph = new int[m][2];

            for (int graphRowItr = 0; graphRowItr < m; graphRowItr++) {
                String[] graphRowItems = scanner.nextLine().split(" ");
                scanner.skip("(rn|[nru2028u2029u0085])*");

                for (int graphColumnItr = 0; graphColumnItr < 2; graphColumnItr++) {
                    int graphItem = Integer.parseInt(graphRowItems[graphColumnItr]);
                    graph[graphRowItr][graphColumnItr] = graphItem;
                }
            }

            int result = crabGraphs(n, t, graph);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;


#define source (0)
#define target (1)

int capacity[300][300];
int flow[300][300];

int max_flow(int n, int s, int t) {
    memset(flow, 0, sizeof(flow));
    int max_flow = 0;
    
    while (true) {
        bool visited[300];
        memset(visited, 0 , sizeof(visited));
        int parent[300];
        
        queue<int> bfs;
        bfs.push(s);
        visited[s] = true;
        parent[s] = -1;        
        
        while (!bfs.empty()) {
            int curr = bfs.front();
            bfs.pop();
            for (int i = 0; i < n; ++i) {
                if (!visited[i] && capacity[curr][i] > flow[curr][i] - flow[i][curr]) {
                    bfs.push(i);
                    parent[i] = curr;
                    visited[i] = true;
                }
                
            }    
        }
        
        if (!visited[t]) { break; }
        
        int path_flow = 0x7FFFFFFF;
        for (int v = t; v != s; v = parent[v])
        {
            int u = parent[v];
            path_flow = min(path_flow, capacity[u][v] - flow[u][v] + flow[v][u]);
        }
 
        // update residual capacities of the edges and reverse edges
        // along the path
        
        for (int v = t; v != s; v = parent[v])
        {
            int u = parent[v];
            flow[u][v] += path_flow;
        }
 
        // Add path flow to overall flow
        max_flow += path_flow;
    }
    return max_flow;
}

#define ODD(x) (2 * (x) + 1)
#define EVEN(x) (2 * (x) + 2)

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int C;
    cin >> C;
    while (C--) {
        memset(capacity, 0, sizeof(capacity));
        int N, T, M;
        cin >> N >> T >> M;
        
        for (int i = 0; i < M; ++i) {
            int v, w;
            cin >> v >> w;
               
            capacity[EVEN(v)][ODD(w)] = 1;
            capacity[EVEN(w)][ODD(v)] = 1;
         }
            
         for (int v = 1; v <= N; ++v) {
             capacity[source][EVEN(v)] = T;
             capacity[ODD(v)][target] = 1;
         }
        
         cout << max_flow(2 * N + 3, source, target) << endl;               
        
    }
    return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min(a, b) ((a)<(b)?(a):(b))

#define NMAX 700
int graph[602][602];
int N;

int BFS(int s, int t, int parent[]){
    int stack[NMAX], i;
    int front = 0, rear = 0;
    int visited[NMAX] = { 0 };

    stack[rear++] = s;

    while (front<rear){
        int v = stack[front++];
        visited[v] = 1;

        for (i = 0; i <= t; i++){
            if (graph[v][i]){

                if (!visited[i]){
                    parent[i] = v;
                    stack[rear++] = i;
                    visited[i] = 1;
                    if (i == t){
                        return 1;
                    }
                }
            }
        }
    }

    return 0;
}

int BPM(){

    int parent[NMAX] = { 0 };
    int i = 0, s = 0;
    parent[s] = -1;
    int t = 2 * N + 1;

    int maxFlow = 0;
    while (BFS(s, t, parent)){
        
        int tmin = INT_MAX;
        for (i = t; i != s; i = parent[i]){
            tmin = min(tmin, graph[parent[i]][i]);
        }

        for (i = t; i != s; i = parent[i]){
            graph[parent[i]][i] -= tmin;
            graph[i][parent[i]] += tmin;
        }

        maxFlow += tmin;
    }

    return maxFlow;
}

int main(){
    int T, tc, K, i, j, M;
    int arr[301];

    scanf("%d", &T);

    for (tc = 0; tc<T; tc++){
        scanf("%d%d%d", &N, &K, &M);

        for (i = 0; i<(2 * N + 2); i++){
            for (j = 0; j<(2 * N + 2); j++){
                graph[i][j] = 0;
            }
        }

        int tree[101][101] = { 0 };
        int u, v;
        for (i = 1; i <= M; i++){
            scanf("%d%d", &u, &v);

            tree[u][0]++;
            tree[u][tree[u][0]] = N+v;

            tree[v][0]++;
            tree[v][tree[v][0]] = N+u;
        }

        for (i = 1; i <= N; i++){
            graph[0][i] = min(tree[i][0], K);
        }

        for (i = 1; i <= N; i++){
            for (j = 1; j <= tree[i][0]; j++){
                graph[i][tree[i][j]] = 1;
            }
        }

        for (i = N + 1; i <= 2 * N; i++){
            graph[i][2 * N + 1] = 1;
        }

        int ans = BPM();
        printf("%dn", ans);
    }
    return 0;
}