HackerRank Tripartite Matching Problem Solution

In this post, we will solve HackerRank Tripartite Matching Problem Solution.

You are given 3 unweighted, undirected graphs, G1, G2, and G3. with n vertices each, where the kth graph has my edges and the vertices in each graph are numbered from 1 through n. Find the number of ordered triples (a, b, c), where 1 < a, b, c <n. ab, bc,ca, such that there is an edge (a, b) in G1, an edge (b, c) in G2, and an edge (c, a) in Ga
Input Format
The first line contains single integer, n. denoting the number of vertices in the graphs. The subsequent lines define G1, G2, and G. Each graph is defined as follows:

The first line contains an integer, m, describing the number of edges in the graph being defined.
Each line i of the m subsequent lines (where 1 < i < m) contains 2 space-separated integers describing the respective nodes, u, and v, connected by edge ¿.

Output Format

Print a single integer denoting the number of distinct (a, b, c) triples as described in the Problem Statement above.

Sample Input

Sample Output

Explanation
There are three possible triples in our Sample Input:

(1,2,3)
(2,1,3)
(3,2,1)
Thus, we print 3 as our output.

HackerRank Tripartite Matching Problem Solution

Tripartite Matching C Solution

#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 1234555
typedef struct _node{
  int x;
  int y;
  struct _node *next;
} node;
typedef struct _lnode{
  int x;
  struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int *len,lnode **table,node **hash);
void insert(node **hash,int x,int y);
int search(node **hash,int x,int y);
int len1[100000],len2[100000],*t1[100000],*t2[100000];
node *hash1[HASH_SIZE],*hash2[HASH_SIZE];
lnode *table1[100000],*table2[100000];

int main(){
  int n,m,x,y,i,j;
  long long ans=0;
  lnode *p;
  scanf("%d",&n);
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,len1,table1,hash1);
  }
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,len2,table2,hash2);
  }
  for(i=0;i<n;i++)
    if(len1[i]){
      t1[i]=(int*)malloc(len1[i]*sizeof(int));
      for(p=table1[i],j=0;p;p=p->next,j++)
        t1[i][j]=p->x;
    }
  for(i=0;i<n;i++)
    if(len2[i]){
      t2[i]=(int*)malloc(len2[i]*sizeof(int));
      for(p=table2[i],j=0;p;p=p->next,j++)
        t2[i][j]=p->x;
    }
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%d%d",&x,&y);
    x--;
    y--;
    if(len1[x]<len2[y])
      for(j=0;j<len1[x];j++)
        ans+=search(hash2,t1[x][j],y);
    else
      for(j=0;j<len2[y];j++)
        ans+=search(hash1,t2[y][j],x);
    if(len1[y]<len2[x])
      for(j=0;j<len1[y];j++)
        ans+=search(hash2,t1[y][j],x);
    else
      for(j=0;j<len2[x];j++)
        ans+=search(hash1,t2[x][j],y);
  }
  printf("%lld",ans);
  return 0;
}
void insert_edge(int x,int y,int *len,lnode **table,node **hash){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->next=table[x];
  table[x]=t;
  len[x]++;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->next=table[y];
  table[y]=t;
  len[y]++;
  insert(hash,x,y);
  insert(hash,y,x);
  return;
}
void insert(node **hash,int x,int y){
  int bucket=(x*100000LL+y)%HASH_SIZE;
  node *t=hash[bucket];
  t=(node*)malloc(sizeof(node));
  t->x=x;
  t->y=y;
  t->next=hash[bucket];
  hash[bucket]=t;
  return;
}
int search(node **hash,int x,int y){
  int bucket=(x*100000LL+y)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->x==x && t->y==y)
      return 1;
    t=t->next;
  }
  return 0;
}

Tripartite Matching C++ Solution

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iterator>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

inline bool isdiff(int a, int b, int c) {
    return a != b && a != c && b != c;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        vector<vpii> gall(n);
        vector<vi> g[3];
        rep(k, 3) {
            g[k].assign(n, vi());
            int m;
            scanf("%d", &m);
            for(int i = 0; i < m; ++ i) {
                int u, v;
                scanf("%d%d", &u, &v), -- u, -- v;
                gall[u].push_back(mp(v, k));
                gall[v].push_back(mp(u, k));
                g[k][u].push_back(v);
                g[k][v].push_back(u);
            }
            rep(i, n)
                sort(all(g[k][i]));
        }
        rep(i, n)
            sort(all(gall[i]));
        vi tmp;
        int ans = 0;
        rep(i, n) for(int j : g[0][i]) if(i != j) {
            const vi &v = g[1][i], &w = g[2][j];
            tmp.clear();
            set_intersection(all(v), all(w), back_inserter<vi>(tmp));
            for(int k : tmp)
                ans += k != i && k != j;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Tripartite Matching C Sharp Solution


using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the tripartiteMatching function below.
     */
    static int tripartiteMatching(int n, long[][] g1, long[][] g2, long[][] g3) {
            var max = Math.Max(g3.Length, Math.Max(g1.Length, g2.Length));
            var adc = new Dictionary<long, Dictionary<long, long>>();
            var cdc = new Dictionary<long, Dictionary<long, long>>();
            var bdc = new Dictionary<long, Dictionary<long, long>>();
            for (var i = 0; i < max; i++)
            {
                if (g1.Length > i)
                {
                    if (!adc.ContainsKey(g1[i][0]))
                    {
                        adc.Add(g1[i][0], new Dictionary<long, long>());
                    }
                    if (!adc.ContainsKey(g1[i][1]))
                    {
                        adc.Add(g1[i][1], new Dictionary<long, long>());
                    }
                    adc[g1[i][0]].Add(g1[i][1], g1[i][1]);
                    adc[g1[i][1]].Add(g1[i][0], g1[i][0]);
                }
                if (g2.Length > i)
                {
                    if (!bdc.ContainsKey(g2[i][0]))
                    {
                        bdc.Add(g2[i][0], new Dictionary<long, long>());
                    }
                    if (!bdc.ContainsKey(g2[i][1]))
                    {
                        bdc.Add(g2[i][1], new Dictionary<long, long>());
                    }
                    bdc[g2[i][0]].Add(g2[i][1], g2[i][1]);
                    bdc[g2[i][1]].Add(g2[i][0], g2[i][0]);
                }
                if (g3.Length > i)
                {
                    if (!cdc.ContainsKey(g3[i][0]))
                    {
                        cdc.Add(g3[i][0], new Dictionary<long, long>());
                    }
                    if (!cdc.ContainsKey(g3[i][1]))
                    {
                        cdc.Add(g3[i][1], new Dictionary<long, long>());
                    }
                    cdc[g3[i][0]].Add(g3[i][1], g3[i][1]);
                    cdc[g3[i][1]].Add(g3[i][0], g3[i][0]);
                }
            }

           // var lst = new List<string>();
            //long a = 0;
            //long b = 0;
           // long c = 0;
            //var akeys = adc.Keys.ToList();
            Dictionary<long, long> vertices = null;
            Dictionary<long, long> bpaths = null;
            Dictionary<long, long> cpath = null;
            int c=0;
            //List<long> acpath = null;
            //Dictionary<long, long> temp = null;
            foreach (var akey in adc)
            {
               // a = akey.Key;
                vertices = adc[akey.Key];//adc[a];
                if (!cdc.ContainsKey(akey.Key)) continue;
                cpath = cdc[akey.Key];
                foreach (var bkey in vertices)
                {
                   // b = bkey.Key;
                    if (!bdc.ContainsKey(bkey.Key) || akey.Key == bkey.Key) continue;
                    // get all paths from b
                    bpaths = bdc[bkey.Key];
                    foreach (var ckey in bpaths)
                    {
                        //c = ckey.Key;
                        if (!cpath.ContainsKey(ckey.Key)|| akey.Key == ckey.Key) continue;

                        //cpath = cdc[ckey.Key];
                       // if (cpath.ContainsKey(akey.Key))
                        //{
                            if (akey.Key != bkey.Key && bkey.Key != ckey.Key && akey.Key != ckey.Key)
                            {
                                //lst.Add($"{akey.Key},{bkey.Key},{ckey.Key}");
                                c++;
                            }
                        //}
                    }
                }
            }

            return c;//lst.Count;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        var n = Convert.ToInt32(Console.ReadLine());

            var m1 = Convert.ToInt64(Console.ReadLine());

            var g1 = new long[m1][];

            for (int g1RowItr = 0; g1RowItr < m1; g1RowItr++)
            {
                g1[g1RowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), g1Temp => Convert.ToInt64(g1Temp));
            }

            var m2 = Convert.ToInt64(Console.ReadLine());

            var g2 = new long[m2][];

            for (int g2RowItr = 0; g2RowItr < m2; g2RowItr++)
            {
                g2[g2RowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), g2Temp => Convert.ToInt64(g2Temp));
            }

            int m3 = Convert.ToInt32(Console.ReadLine());

            var g3 = new long[m3][];

            for (int g3RowItr = 0; g3RowItr < m3; g3RowItr++)
            {
                g3[g3RowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), g3Temp => Convert.ToInt64(g3Temp));
            }

        int result = tripartiteMatching(n, g1, g2, g3);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Tripartite Matching Java Solution

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class D {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    int[][] read(int n)
    {
        int m = ni();
        int[] from = new int[m];
        int[] to = new int[m];
        for(int i = 0;i < m;i++){
            from[i] = ni()-1;
            to[i] = ni()-1;
        }
        return packU(n, from, to);
    }
    
    void solve()
    {
        int n = ni();
        int[][] ga = read(n);
        int[][] gb = read(n);
        int[][] gc = read(n);
        
        int S = (int)Math.sqrt(100000);
        long[][] gbb = new long[n][];
        long[][] gbc = new long[n][];
        for(int i = 0;i < n;i++){
            if(gb[i].length >= S){
                gbb[i] = new long[(n>>>6)+1];
                for(int e : gb[i]){
                    gbb[i][e>>>6] |= 1L<<e;
                }
            }
            if(gc[i].length >= S){
                gbc[i] = new long[(n>>>6)+1];
                for(int e : gc[i]){
                    gbc[i][e>>>6] |= 1L<<e;
                }
            }
            Arrays.sort(gb[i]);
            Arrays.sort(gc[i]);
        }
        
        int na = ga.length;
        long ret = 0;
        for(int a = 0;a < na;a++){
            for(int b : ga[a]){
                if(gbb[b] != null){
                    if(gbc[a] != null){
                        for(int i = 0;i < (n>>>6)+1;i++){
                            ret += Long.bitCount(gbb[b][i]&gbc[a][i]);
                        }
                    }else{
                        for(int e : gc[a]){
                            if(gbb[b][e>>>6]<<~e<0)ret++;
                        }
                    }
                }else{
                    if(gbc[a] != null){
                        for(int e : gb[b]){
                            if(gbc[a][e>>>6]<<~e<0)ret++;
                        }
                    }else{
                        for(int i = 0, j = 0;i < gb[b].length && j < gc[a].length;){
                            if(gb[b][i] == gc[a][j]){
                                ret++; i++; j++;
                            }else if(gb[b][i] < gc[a][j]){
                                i++;
                            }else{
                                j++;
                            }
                        }
                    }
                }
            }
        }
        out.println(ret);
    }
    
    static int[][] packU(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++) {
            g[from[i]][--p[from[i]]] = to[i];
            g[to[i]][--p[to[i]]] = from[i];
        }
        return g;
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new D().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Tripartite Matching 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', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the tripartiteMatching function below.
 */
class Vertex {
    constructor(number) {
        this.number = number;
        this.edges_g1 = {};
        this.edges_g2 = {};
        this.edges_g3 = {};
    }
}
        

class Graph {
    constructor(vertex_count) {
        this.n = vertex_count;
        this.vertices = {};
        for (let i = 1; i <= vertex_count; i++) {
            this.vertices[i] = new Vertex(i);
        }
    }
    
    load_edges(graph, pairs) {
        pairs.forEach((edge) => {
            if (edge[0] <= this.n && edge[1] <= this.n) {
                this.add_edge(graph, edge[0], edge[1])
            }    
        }) 
    }

    add_edge(graph, v1, v2) {
        this.vertices[v1][`edges_${graph}`][v2] = true;
        this.vertices[v2][`edges_${graph}`][v1] = true;  
    }
}
/*
# Complete the tripartiteMatching function below.
*/
function tripartiteMatching(n, g1, g2, g3) {
    // g1 = [[1, 2], [2, 3]]
    // Write your code here.
    // Actually build the graph, annotate vertexes with available edges per graph 
    const graph = new Graph(n);
    graph.load_edges('g1', g1);
    graph.load_edges('g2', g2);
    graph.load_edges('g3', g3);

    let trips = 0;
    Object.keys(graph.vertices).forEach((a) => {
        let vertex = graph.vertices[a];
        Object.keys(vertex.edges_g1).forEach((b) => {
            if (a != b) {
                Object.keys(graph.vertices[b].edges_g2).forEach((c) => {
                    if (c != b && c != a && graph.vertices[c].edges_g3[a]) {
                        trips++;
                    }
                })
            }
        })
    }); 
    return trips;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine(), 10);

    const m1 = parseInt(readLine(), 10);

    let g1 = Array(m1);

    for (let g1RowItr = 0; g1RowItr < m1; g1RowItr++) {
        g1[g1RowItr] = readLine().split(' ').map(g1Temp => parseInt(g1Temp, 10));
    }

    const m2 = parseInt(readLine(), 10);

    let g2 = Array(m2);

    for (let g2RowItr = 0; g2RowItr < m2; g2RowItr++) {
        g2[g2RowItr] = readLine().split(' ').map(g2Temp => parseInt(g2Temp, 10));
    }

    const m3 = parseInt(readLine(), 10);

    let g3 = Array(m3);

    for (let g3RowItr = 0; g3RowItr < m3; g3RowItr++) {
        g3[g3RowItr] = readLine().split(' ').map(g3Temp => parseInt(g3Temp, 10));
    }

    let result = tripartiteMatching(n, g1, g2, g3);

    ws.write(result + "\n");

    ws.end();
}

Tripartite Matching Python Solution

#!/bin/python3

import os
import sys

#
# Complete the tripartiteMatching function below.
#
vertices = int(input())
graph = [[], [], [], []]
count = 0
G1 = 1
G2 = 2
G3 = 3

for i in range(1, 4):
    for j in range(0, vertices + 1):
        graph[i].append(None)

for i in range(1, 4):
    edges = int(input())
    for j in range(0, edges):
        edge = list(map(int, input().split(" ")))
        if graph[i][edge[0]] is None:
            graph[i][edge[0]] = set()
        graph[i][edge[0]].add(edge[1])
        if graph[i][edge[1]] is None:
            graph[i][edge[1]] = set()
        graph[i][edge[1]].add(edge[0])

for vertex in range(1, vertices + 1):
    verticesToG1 = graph[G1][vertex]
    if verticesToG1 is not None:
        verticesFromG2 = graph[G2][vertex]
        if verticesFromG2 is not None:
            for toVertex in verticesFromG2:
                verticesFromG3 = graph[G3][toVertex]
                if verticesFromG3 is not None:
                    count = count + len(verticesToG1.intersection(verticesFromG3))
        
print(count)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python