We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Tripartite Matching
  5. Discussions

Tripartite Matching

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 10 Discussions, By:

votes

Please Login in order to post a comment

  • kissgergely
    4 years ago+ 0 comments

    In the task description it is written that:

    • the graphs are unweighted and undirected
    • "Each graph contains no cycles and any pair of directly connected nodes is connected by a maximum of edge."

    But in the sample input the second graph is the following:

    3
    1 2
    1 3
    2 3
    

    Which contains a cycle. What am I misunderstanding? I would really appriciate some help.

    3|
    Permalink
  • TChalla
    1 year ago+ 0 comments
    import sys
    
    def main():
        N = int(sys.stdin.readline())
        M = []
        G = []
        for i in range(3):
            M.append(int(sys.stdin.readline()))
            G.append([set() for _ in range(N)])
            for _ in range(M[i]):
                u, v = map(int, sys.stdin.readline().split())
                u, v = u - 1, v - 1
                G[i][u].add(v)
                G[i][v].add(u)
        cpt = 0
        for a in range(N):
            for b in G[0][a]:
                for c in G[1][b]:
                    if a in G[2][c]:
                        #print a,b,c
                        cpt += 1
        print(cpt)
    
    main()
    
    0|
    Permalink
  • worc19966d
    2 years ago+ 0 comments

    Its impossible to complete in c# without modfying the process of reading data from console (one must modify Main method)

    0|
    Permalink
  • jordanwrhinehart
    5 years ago+ 0 comments

    Are there not 6 possible triples on the sample input?

    0|
    Permalink
  • tamagochii
    5 years ago+ 0 comments

    Just a very unelegant approach ,the first two graphs are lists so that I can go through them in a for loop which is faster than a for each and the third is a hashset because I need a O(1) contains. Only one testcase times out.The others pass.

    using System;
    using System.Collections.Generic;
    
    class Triparte_Matching
    {
        static int n;
        static List<int>[] firstGraph, secondGraph;
        static HashSet<int>[] thirdGraph;
    
        static void Main(string[] args)
        {
            ReadInput();
            Console.WriteLine(Solve());
        }
    
        private static int Solve()
        {
            var res = 0;
    
            for (int i = 0; i < firstGraph.Length; i++)
            {
                if (firstGraph[i] == null)
                {
                    continue;
                }
    
                for (int j = 0; j < firstGraph[i].Count; j++)
                {
                    var num = firstGraph[i][j];
                    if (secondGraph[num] == null || num == i)
                    {
                        continue;
                    }
    
                    for (int p = 0; p < secondGraph[num].Count; p++)
                    {
                        var secondNum = secondGraph[num][p];
                        if (num != i && secondNum != i && thirdGraph[secondNum] != null && thirdGraph[secondNum].Contains(i))
                        {
                            res++;
                        }
                    }
                }
            }
    
            return res;
        }
    
        private static void ReadInput()
        {
            n = int.Parse(Console.ReadLine());
            firstGraph = new List<int>[n + 1];
            secondGraph = new List<int>[n + 1];
            thirdGraph = new HashSet<int>[n + 1];
    
            var m = int.Parse(Console.ReadLine());
            string[] args;
    
            for (int i = 0; i < m; i++)
            {
                args = Console.ReadLine().Split(' ');
                var start = int.Parse(args[0]);
                var end = int.Parse(args[1]);
                if (firstGraph[start] == null)
                {
                    firstGraph[start] = new List<int>();
                }
                if (firstGraph[end] == null)
                {
                    firstGraph[end] = new List<int>();
                }
                firstGraph[start].Add(end);
                firstGraph[end].Add(start);
            }
    
            m = int.Parse(Console.ReadLine());
            for (int i = 0; i < m; i++)
            {
                args = Console.ReadLine().Split(' ');
                var start = int.Parse(args[0]);
                var end = int.Parse(args[1]);
                if (secondGraph[start] == null)
                {
                    secondGraph[start] = new List<int>();
                }
                if (secondGraph[end] == null)
                {
                    secondGraph[end] = new List<int>();
                }
                secondGraph[start].Add(end);
                secondGraph[end].Add(start);
            }
    
            m = int.Parse(Console.ReadLine());
            for (int i = 0; i < m; i++)
            {
                args = Console.ReadLine().Split(' ');
                var start = int.Parse(args[0]);
                var end = int.Parse(args[1]);
                if (thirdGraph[start] == null)
                {
                    thirdGraph[start] = new HashSet<int>();
                }
                if (thirdGraph[end] == null)
                {
                    thirdGraph[end] = new HashSet<int>();
                }
                thirdGraph[start].Add(end);
                thirdGraph[end].Add(start);
            }
        }
    }
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature