In this HackerRank Jogging Cats problem solution Given a map of the city, can you help our heroic cats determine the maximum number of days they can go jogging so that every route traveled is different?

## Problem solution in Java.

```import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int K = 150;
int n = sc.nextInt();
int m = sc.nextInt();

ArrayList<Integer>[] edgesList = new ArrayList[n];

for (int i = 0; i < n; ++i) {
edgesList[i] = new ArrayList<>();
}
for (int i = 0; i < m; ++i) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
}

int[][] edges = new int[n][];
for (int i = 0; i < n; ++i) {
edges[i] = new int[edgesList[i].size()];
for (int it = 0; it < edges[i].length; ++it) {
edges[i][it] = edgesList[i].get(it);
}
Arrays.sort(edges[i]);
}
long[] ar = new long[m * K];
int arLen = 0;
long ans = 0;
boolean[] col = new boolean[n];
for (int i = 0; i < n; ++i) {
if (edges[i].length <= K) {
for (int it = 0; it < edges[i].length; ++it) {
for (int jt = it + 1; jt < edges[i].length; ++jt) {
ar[arLen++] = n * edges[i][it] + edges[i][jt];
}
}
} else {
Arrays.fill(col, false);
for (int j : edges[i]) {
col[j] = true;
}
for (int j = 0; j < n; ++j) {
if (edges[j].length > K && j <= i) {
continue;
}
long cnt = 0;
for (int k : edges[j]) {
if (col[k]) {
cnt++;
}
}
ans += cnt * (cnt - 1) / 2;
}
}
}
Arrays.sort(ar, 0, arLen);
for (int i = 0; i < arLen; ) {
int j = i;
while (j < ar.length && ar[i] == ar[j]) {
++j;
}
long cnt = j - i;
ans += cnt * (cnt - 1) / 2;
i = j;
}
if (ans % 2 != 0) {
throw new AssertionError();
}
System.out.println(ans/2);
}
}
```

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

## Problem solution in C++.

```#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
#include <set>

using namespace std;

const int MAXN = 50000 + 10;

int n, m, ans[5], wn, w[MAXN], x, y;
int am[MAXN][MAXN / 30 + 10];
long long ans4;

inline bool exists_edge (int x, int y) {
return ((am[x][y / 30] & (1 << (y % 30))) > 0);
}

const int MAX_BIG_NODES = 4000;

int p[MAX_BIG_NODES][MAX_BIG_NODES], big_index[MAXN], big_nodes, q[MAX_BIG_NODES][MAX_BIG_NODES];

void count_4cliques () {
int threshold = (int)exp(log(n * 1.0) / 3.0);
for(int i = 1; i <= n; i++) if (adj[i].size() >= threshold)
big_index[i] = ++big_nodes;
for(int i = 1; i <= n; i++) for(int j = 0; j < adj[i].size(); j++) {
}
// 4 big nodes
long long ans_4big = 0;
for(int i = 1; i <= n; i++) if (big_index[i]) for(int j = 0; j < adj_big[i].size(); j++) {
int x = big_index[i];
for(int k = 0; k < adj_big[xy].size(); k++) {
if (z && z != x)
ans_4big += p[x][z]++;
}
}
// 3 big nodes
long long ans_3big = 0;
for(int i = 1; i <= n; i++) if (!big_index[i]) {
for(int j = 0; j < adj_big[i].size(); j++) {
for(int k = j + 1; k < adj_big[i].size(); k++) {
ans_3big += p[x][y];
}
}
}
// 2 big nodes lie diagonally
long long ans_2big_diagonal = 0;
for(int i = 1; i <= n; i++) if (!big_index[i]) {
for(int j = 0; j < adj_big[i].size(); j++) {
for(int k = j + 1; k < adj_big[i].size(); k++) {
ans_2big_diagonal += q[min(x, y)][max(x, y)]++;
}
}
}
// 2 big nodes are connected
long long ans_2big_conn = 0;
for(int i = 1; i <= n; i++) if (!big_index[i]) {
for(int a = 0; a < adj_big[i].size(); a++)
for(int b = 0; b < adj_big[y].size(); b++) {
ans_2big_conn += exists_edge(qa, qb);
}
}
}
// 1 big node OR 0 big nodes
long long ans_1big = 0;
long long ans_0big = 0;
for(int i = 1; i <= n; i++) if (!big_index[i]) {
for(int k = j + 1; k < adj[i].size(); k++) if (!big_index[adj[i][k]]) {
}
}
}
ans4 = ans_4big / 4 + ans_3big + ans_2big_conn / 2 + ans_2big_diagonal + ans_1big + ans_0big / 4;
}

int main () {
set<pair<int, int> > edges;
cin >> n >> m;
assert(1 <= n && n <= 50000);
assert(1 <= m && m <= 100000);
for(int i = 1; i <= m; i++) {
cin >> x >> y;
assert(1 <= x && x <= n);
assert(1 <= y && y <= n);
assert(x != y);
edges.insert(make_pair(min(x, y), max(x, y)));
am[x][y / 30] |= (1 << (y % 30));
am[y][x / 30] |= (1 << (x % 30));
}
assert(edges.size() == m);
count_4cliques();
cout << ans4 << 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>

char** split_string(char*);

struct edge{
int from;
int to;
};

bool precedge(struct edge e1, struct edge e2){
return e1.from < e2.from || (e1.from == e2.from && e1.to < e2.to);
}

void setup(int n, int m, int** edges, struct edge *sortedge, int* edgebds){
for(int i = 0; i < m; i++){
sortedge[2*i].from = edges[i][0] - 1;
sortedge[2*i].to = edges[i][1] - 1;
sortedge[2*i + 1].from = edges[i][1] - 1;
sortedge[2*i + 1].to = edges[i][0] - 1;
}

for(int i = 0; i < 2*m; i++){
int curr = i;
while(curr > 0){
int next = (curr - 1)/2;
if(precedge(sortedge[next], sortedge[curr])){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}

for(int i = 2*m - 1; i >= 0; i--){
struct edge temp = sortedge[0];
sortedge[0] = sortedge[i];
sortedge[i] = temp;

int curr = 0;
while(true){
int next = curr;
if(2*curr + 1 < i && precedge(sortedge[next], sortedge[2*curr + 1])){
next = 2*curr + 1;
}
if(2*curr + 2 < i && precedge(sortedge[next], sortedge[2*curr + 2])){
next = 2*curr + 2;
}
if(next != curr){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}

edgebds[0] = 0;
for(int i = 0; i < n; i++){
int index = edgebds[i];
while(index < 2*m && sortedge[index].from == i){
index++;
}
edgebds[i + 1] = index;
}
}

long jogroutes(int n, int m, int** edges){
struct edge sortedge[2*m];
int edgebounds[n + 1];
setup(n, m, edges, sortedge, edgebounds);
long toreturn = 0;
for(int i = 0; i < n; i++){
int start = edgebounds[i];
for(; start < edgebounds[i + 1] && sortedge[start].to < i; start++);

int numneighbors = edgebounds[i + 1] - start;
if(numneighbors > 50){
for(int j = i + 1; j < n; j++){
if(edgebounds[j] + 1 < edgebounds[j + 1]){
long common = 0;
int index1 = start;
int index2 = edgebounds[j];
while(index1 < edgebounds[i + 1] && index2 < edgebounds[j + 1]){
if(sortedge[index1].to == sortedge[index2].to){
common++;
index1++;
index2++;
}
else if(sortedge[index1].to > sortedge[index2].to){
index2++;
}
else{
index1++;
}
}
toreturn += common*(common - 1);
}
}
}
else{
for(int j = start; j < edgebounds[i + 1]; j++){
int node1 = sortedge[j].to;
int nextstart = edgebounds[node1];
for(; nextstart < edgebounds[node1 + 1] && sortedge[nextstart].to <= i; nextstart++);
for(int k = j + 1; k < edgebounds[i + 1]; k++){
int node2 = sortedge[k].to;
int index1 = nextstart;
int index2 = edgebounds[node2];
while (index1 < edgebounds[node1 + 1] && index2 < edgebounds[node2 + 1]){
if(sortedge[index1].to == sortedge[index2].to){
toreturn += 2;
index1++;
index2++;
}
else if(sortedge[index1].to > sortedge[index2].to){
index2++;
}
else{
index1++;
}
}
}
}
}
}
}

int main() {
int n, m;
scanf("%d %d\n", &n, &m);
int** edges = malloc(m*sizeof(int*));
for(int i = 0; i < m; i++){
edges[i] = malloc(2*sizeof(int));
scanf("%d %d\n", edges[i], edges[i] + 1);
}
long result = jogroutes(n, m, edges);
printf("%ld", result);
return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}

char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");

int spaces = 0;

while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}

splits[spaces - 1] = token;

token = strtok(NULL, " ");
}

return splits;
}
```

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