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.

HackerRank Crab Graphs problem solution


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)

{"mode":"full","isActive":false}


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("(\r\n|[\n\r\u2028\u2029\u0085])*");

        for (int cItr = 0; cItr < c; cItr++) {
            String[] ntm = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            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("(\r\n|[\n\r\u2028\u2029\u0085])*");

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

{"mode":"full","isActive":false}


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

{"mode":"full","isActive":false}


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("%d\n", ans);
    }
    return 0;
}

{"mode":"full","isActive":false}