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.
Tripartite Matching
Tripartite Matching
+ 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.
+ 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 comments Its impossible to complete in c# without modfying the process of reading data from console (one must modify Main method)
+ 0 comments Are there not 6 possible triples on the sample input?
+ 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); } } }
Load more conversations
Sort 10 Discussions, By:
Please Login in order to post a comment