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