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