# 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)
```

{"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) {
for (int i = 0; i < n; i++) {
}
for (int[] edge : graph) {
int n1 = edge[0] - 1;
int n2 = edge[1] - 1;
}

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

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

cover--;
} else {
}
}
}
}
}
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}