In this post, we will solve HackerRank Crab Graphs Problem Solution.
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1 <= K <= T, where T is given)
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.
Note: two graphs are vertex-disjoint if they do not have any vertices in common.
Input Format
The first line of input contains a single integer C. C test-cases follow. The first line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated values v1i, v2i meaning that the there is an edge between vertices v1i and v2i. Note that the graph doesn’t have parallel edges or loops.
Constraints
- 1 <= C <= 10
- 2 <= T <= 100
- 2 <= N <= 100
- 0 <= M <= N * (N-1)/2
- 1 <= v1i <= N
- 1 <= v2i <= N
Output Format
For each test-case, output a single integer indicating the maximum number of vertices which can be covered by vertex-disjoint sub-graphs of crab- graphs.
Sample Input
2
8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6
6 3 8
1 2
2 3
3 4
4 5
5 6
6 1
1 4
2 5
Sample Output
6
6
Explanation
Test #1: The graph for this test-case below. Because T = 2, each crab can have a maximum of 2 feet => each crab can cover a maximum of 3 nodes. We can cover 6 nodes of this graph with these two crabs: One of the crabs has 4 as its head and 1 and 3 as its feet, the other crab has 5 as its head and 7 and 8 as its feet. No additional crabs can be added.
The above is not a unique solution: any combination of two crabs, with one head at 4 and one head at 5, will suffice. We could have also chosen Head[4]feet[1,2] and Head[5]feet[6,7] as our two crabs.
Test #2: The graph for this test-case below. We can cover all 6 nodes using two crabs. One of the crabs has 2 as its head and 1 and 3 as its feet, the other crab has 5 as its head and 4 and 6 as its feet.
Crab Graphs C Solution
#include <stdio.h>
#include <stdlib.h>
void remove_edge(int x,int y,int*connection,int**matrix);
void remove_point(int x,int*connection,int**matrix,int size);
void remove_point2(int x,int y,int*connection,int**matrix,int size);
int main()
{
int i,j,k,C,T,N,M,x,y,ans,flag;
int**matrix,*connection,*temp_connection;
matrix=(int**)malloc(101*sizeof(int*));
for(i=0;i<101;i++)
matrix[i]=(int*)malloc(101*sizeof(int));
connection=(int*)malloc(101*sizeof(int));
temp_connection=(int*)malloc(101*sizeof(int));
scanf("%d",&C);
for(i=0;i<C;i++){
scanf("%d%d%d",&N,&T,&M);
ans=N;
for(j=0;j<=N;j++)
connection[j]=temp_connection[j]=0;
for(j=0;j<=N;j++)
for(k=0;k<=N;k++)
matrix[j][k]=0;
for(j=0;j<M;j++){
scanf("%d%d",&x,&y);
matrix[x][y]=matrix[y][x]=1;
connection[x]++;
connection[y]++;
}
for(j=1;j<=N;j++)
if(!connection[j])
ans--;
do{
flag=0;
for(j=1;j<=N;j++)
for(k=1;k<=N;k++)
if(matrix[j][k]&&connection[j]==1&&connection[k]==1)
remove_edge(j,k,connection,matrix);
else if(matrix[j][k]&&connection[k]==1){
flag=1;
temp_connection[j]++;
}
for(j=1;flag&&j<=N;j++)
if(temp_connection[j]>=T){
flag=2;
ans-=temp_connection[j]-T;
remove_point(j,connection,matrix,N);
}
else if(temp_connection[j]&&temp_connection[j]==connection[j]){
flag=2;
remove_point(j,connection,matrix,N);
}
if(flag==1)
for(j=1;flag==1&&j<=N;j++)
for(k=1;flag==1&&k<=N;k++)
if(matrix[j][k]&&temp_connection[j]&&connection[k]!=1){
flag=2;
remove_point2(k,j,connection,matrix,N);
}
for(j=1;j<=N;j++)
temp_connection[j]=0;
}while(flag);
printf("%d\n",ans);
}
return 0;
}
void remove_edge(int x,int y,int*connection,int**matrix)
{
connection[x]--;
connection[y]--;
matrix[x][y]=matrix[y][x]=0;
return;
}
void remove_point(int x,int*connection,int**matrix,int size)
{
int i;
for(i=1;i<=size;i++)
if(matrix[x][i])
remove_edge(x,i,connection,matrix);
return;
}
void remove_point2(int x,int y,int*connection,int**matrix,int size)
{
int i;
for(i=1;i<=size;i++)
if(matrix[x][i]&&i!=y)
remove_edge(x,i,connection,matrix);
return;
}Crab Graphs C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <array>
#include <queue>
#include <unordered_map>
#include <stdio.h>
using namespace std;
using edge_t = int64_t;
edge_t as_edge(int a, int b) {
return ((edge_t)a << (edge_t)32) | b;
}
int get_a(edge_t e) {
return e >> 32;
}
int get_b(edge_t e) {
return e & 0xFFFFFFFF;
}
int main() {
int C;
scanf("%d", &C);
while(C--) {
int N, T, M;
scanf("%d %d %d", &N, &T, &M);
const int S = 200;
const int D = 201;
const int MAX = 202;
std::array<std::vector<int>, 100> Graph;
for(int i=0; i<M; ++i) {
int a, b;
scanf("%d %d", &a, &b);
--a; --b;
Graph[a].push_back(b);
Graph[b].push_back(a);
}
std::array<std::vector<int>, MAX> RG;
std::unordered_map<edge_t, int> EF;
auto add_edge = [&RG, &EF](int from, int to, int c)
{
RG[from].push_back(to);
EF[as_edge(from, to)] = c;
RG[to].push_back(from);
EF[as_edge(to, from)] = 0;
};
for(int i=0; i<N; ++i) {
int d = (int)Graph[i].size();
int cap = std::min(d, T);
add_edge(S, i*2, cap);
add_edge(i*2+1, D, 1);
for(int j=0; j<d; ++j) {
int v1 = Graph[i][j];
if(i < v1) {
add_edge(i*2, v1*2+1, 1);
add_edge(v1*2, i*2+1, 1);
}
}
}
std::queue<int> Q;
std::array<int, MAX> Prev;
int maxflow = 0;
while(1) {
while(!Q.empty()) {
Q.pop();
}
Q.push(S);
for(int v=0; v<2*N; ++v) {
Prev[v] = -1;
}
Prev[S] = -2;
Prev[D] = -1;
while(!Q.empty()) {
int v = Q.front();
Q.pop();
for(auto v1 : RG[v]) {
int f = EF[as_edge(v, v1)];
if((f > 0) && Prev[v1] == -1) {
Prev[v1] = v;
Q.push(v1);
}
}
if(Prev[D] != -1) {
break;
}
}
if(Prev[D] == -1) {
break;
}
int fc = 1000000;
int v1 = D;
while(Prev[v1] != -2) {
int v = Prev[v1];
fc = std::min(fc, EF[as_edge(v, v1)]);
v1 = v;
}
v1 = D;
while(Prev[v1] != -2) {
int v = Prev[v1];
EF[as_edge(v, v1)] -= fc;
EF[as_edge(v1, v)] += fc;
if(v == S) {
maxflow += fc;
}
v1 = v;
}
}
printf("%d\n", maxflow);
}
return 0;
}Crab Graphs C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
/*
* Complete the 'crabGraphs' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER t
* 3. 2D_INTEGER_ARRAY graph
*/
private static List<List<int>> ed;
private static bool[,] f;
public static int crabGraphs(int n, int t, List<List<int>> graph)
{
int res = 0, n1, n2, mk;
ed = new List<List<int>>();
f = new bool[2 * n + 2, 2 * n + 2];
for (int i = 0; i <= 2 * n + 1; i++)
{
ed.Add(new List<int>());
}
for (int i = 0; i < graph.Count; i++)
{
n1 = graph[i][0];
n2 = graph[i][1];
ed[2 * n1].Add(2 * n2 + 1);
ed[2 * n2 + 1].Add(2 * n1);
ed[2 * n2].Add(2 * n1 + 1);
ed[2 * n1 + 1].Add(2 * n2);
f[2 * n2 + 1, 2 * n1] = true;
f[2 * n1 + 1, 2 * n2] = true;
}
for (int i = 1; i <= n; i++)
{
mk = 0;
for (int j = 0; j < ed[2 * i].Count && mk < t; j++)
{
n1 = 2 * i;
n2 = ed[n1][j];
if (f[n1, n2]) continue;
if (doIt(n1, n2, n))
{
res++;
mk++;
}
}
}
return res;
}
private static bool doIt(int i, int t, int n)
{
int[] trac = new int[2*n + 2];
int yk, tk, y;
bool[] b = new bool[2 * n + 2];
Queue<int> q = new Queue<int>();
q.Enqueue(t);
trac[t] = i;
b[i] = true;
while (q.Count > 0)
{
yk = q.Peek();
q.Dequeue();
b[yk] = true;
if (yk % 2 == 1 && !f[yk, 0])
{
f[yk, 0] = true;
while (trac[yk]!=0)
{
tk = yk;
yk = trac[yk];
f[yk, tk] = true;
f[tk, yk] = false;
}
return true;
}
else
{
y = ed[yk].Count;
for (int j = 0; j < y; j++)
{
if (!b[ed[yk][j]] && !f[yk, ed[yk][j]])
{
q.Enqueue(ed[yk][j]);
b[ed[yk][j]] = true;
trac[ed[yk][j]] = yk;
}
}
}
}
return false;
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int c = Convert.ToInt32(Console.ReadLine().Trim());
for (int cItr = 0; cItr < c; cItr++)
{
string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
int n = Convert.ToInt32(firstMultipleInput[0]);
int t = Convert.ToInt32(firstMultipleInput[1]);
int m = Convert.ToInt32(firstMultipleInput[2]);
List<List<int>> graph = new List<List<int>>();
for (int i = 0; i < m; i++)
{
graph.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(graphTemp => Convert.ToInt32(graphTemp)).ToList());
}
int result = Result.crabGraphs(n, t, graph);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}Crab Graphs Java Solution
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();
}
}Crab Graphs JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'crabGraphs' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER t
* 3. 2D_INTEGER_ARRAY graph
*/
function crabGraphs(n, t, graph) {
const NODE_COUNT = n, CRAB_LIMIT = t;
let nodesCount = [], nodesEdges = [];
for (let j = 0; j <= NODE_COUNT; j++) {
nodesCount[j] = 0;
nodesEdges.push([]);
}
for (let edge of graph) {
nodesCount[edge[0]] += 1;
nodesCount[edge[1]] += 1;
nodesEdges[edge[0]].push(edge[1]);
nodesEdges[edge[1]].push(edge[0]);
}
let remove = true;
while (remove && Math.max(...nodesCount) > CRAB_LIMIT) {
remove = false;
for (let j = 1; j <= NODE_COUNT; j++) {
if (nodesCount[j] == 1) {
let ind = nodesEdges[j][0]
for (let lar of nodesEdges[ind]) {
if (nodesCount[lar] > CRAB_LIMIT) {
nodesCount[ind] -= 1;
nodesCount[lar] -= 1;
nodesEdges[ind].splice(nodesEdges[ind].indexOf(lar), 1);
nodesEdges[lar].splice(nodesEdges[lar].indexOf(ind), 1);
remove = true;
}
}
}
}
}
while (Math.max(...nodesCount) > CRAB_LIMIT) {
let ind = nodesCount.indexOf(Math.max.apply(null, nodesCount));
let maxEdg = nodesEdges[ind][0];
for (let edg of nodesEdges[ind])
if (nodesEdges[edg].length > nodesEdges[maxEdg].length)
maxEdg = edg;
nodesCount[ind] -= 1;
nodesCount[maxEdg] -= 1;
nodesEdges[ind].splice(nodesEdges[ind].indexOf(maxEdg), 1);
nodesEdges[maxEdg].splice(nodesEdges[maxEdg].indexOf(ind), 1);
}
let cou = nodesCount.filter(nc => nc > 0).length;
return cou;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const c = parseInt(readLine().trim(), 10);
for (let cItr = 0; cItr < c; cItr++) {
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const n = parseInt(firstMultipleInput[0], 10);
const t = parseInt(firstMultipleInput[1], 10);
const m = parseInt(firstMultipleInput[2], 10);
let graph = Array(m);
for (let i = 0; i < m; i++) {
graph[i] = readLine().replace(/\s+$/g, '').split(' ').map(graphTemp => parseInt(graphTemp, 10));
}
const result = crabGraphs(n, t, graph);
ws.write(result + '\n');
}
ws.end();
}Crab Graphs Python Solution
#!/bin/python3
import os
import sys
#
# Complete the crabGraphs function below.
#
from collections import defaultdict
#This class represents a directed graph using adjacency matrix representation
class Graph:
def __init__(self,graph):
self.graph = graph # residual graph
self. ROW = len(graph)
#self.COL = len(gr[0])
'''Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path '''
def BFS(self,s, t, parent):
#print("dans BFS({}, {})".format(s,t))
# Mark all the vertices as not visited
visited =[False]*(self.ROW)
# Create a queue for BFS
queue=[]
# Mark the source node as visited and enqueue it
queue.append(s)
visited[s] = True
# Standard BFS Loop
while queue:
#Dequeue a vertex from queue and print it
u = queue.pop(0)
#print("on dequeue {}".format(u))
# Get all adjacent vertices of the dequeued vertex u
# If a adjacent has not been visited, then mark it
# visited and enqueue it
for ind, val in enumerate(self.graph[u]):
if visited[ind] == False and val > 0 :
#print("on rajoute {}".format(ind))
queue.append(ind)
visited[ind] = True
parent[ind] = u
#print("Fin BFS, on imprime parent:")
#for i, p in enumerate(parent): print("parent[{}] = {}".format(i, p))
# If we reached sink in BFS starting from source, then return
# true, else false
return True if visited[t] else False
# Returns tne maximum flow from s to t in the given graph
def FordFulkerson(self, source, sink):
# This array is filled by BFS and to store path
parent = [-1]*(self.ROW)
#print("on imprime parent:")
#for i, p in enumerate(parent): print("parent[{}] = {}".format(i, p))
max_flow = 0 # There is no flow initially
# Augment the flow while there is path from source to sink
while self.BFS(source, sink, parent) :
# Find minimum residual capacity of the edges along the
# path filled by BFS. Or we can say find the maximum flow
# through the path found.
path_flow = sys.maxsize
s = sink
while(s != source):
path_flow = min (path_flow, self.graph[parent[s]][s])
s = parent[s]
# Add path flow to overall flow
max_flow += path_flow
# update residual capacities of the edges and reverse edges
# along the path
v = sink
while(v != source):
u = parent[v]
self.graph[u][v] -= path_flow
self.graph[v][u] += path_flow
v = parent[v]
return max_flow
def crabGraphs(n, t, graph):
#
# Write your code here.
#
g = Graph(graph)
return g.FordFulkerson(0, 1)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
c = int(input())
for c_itr in range(c):
ntm = input().split()
n = int(ntm[0])
t = int(ntm[1])
m = int(ntm[2])
graph = [[0 for _ in range(2*n+2)] for _ in range(2*n+2)]
degree = [0 for _ in range(2*n+2)]
for _ in range(m):
u, v = list(map(int, input().rstrip().split()))
graph[2*u][2*v+1] = 1
degree[2*u] += 1
graph[2*v][2*u+1] = 1
degree[2*v] += 1
for k in range(2, 2*n+2, 2):
graph[0][k] = min(t, degree[k])
graph[k+1][1]=1
result = crabGraphs(n, t, graph)
fptr.write(str(result) + '\n')
fptr.close()
