HackerRank Crab Graphs problem solution

In this HackerRank Crab Graphs problem solution, you have 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.

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)

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;
}