Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Friendless Dr. Sheldon Cooper MST
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//Rextester.Program.Main is the entry point for your code. Don't change it. //Microsoft (R) Visual C# Compiler version 2.9.0.63208 (958f2354) using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace Rextester { public class Program { /* // Sample code to perform I/O: name = Console.ReadLine(); // Reading input from STDIN Console.WriteLine("Hi, {0}.", name); // Writing output to STDOUT // Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail */ // Write your code here private class Edge { public int Src { get; set; } public int Dest { get; set; } } private class UnionFind { private readonly int[] m_parent; private readonly int[] m_size; public UnionFind(int numVertices) { m_parent = new int[numVertices + 1]; for (var i = 0; i <= numVertices; i++) { m_parent[i] = i; } m_size = new int[numVertices + 1]; } private int FindParent(int node) { while (node != m_parent[node]) { m_parent[node] = m_parent[m_parent[node]]; node = m_parent[node]; } return node; } public bool IsConnected(int u, int v) { var uParent = FindParent(u); var vParent = FindParent(v); return uParent == vParent; } public void Union (int u, int v) { var uParent = FindParent(u); var vParent = FindParent(v); if (uParent == vParent) { return; } if (m_size[u] < m_size[v]) { m_parent[u] = v; m_size[v] += m_size[u]; } else { m_parent[v] = u; m_size[u] += m_size[v]; } } } public static void Main(string[] args) { var t = int.Parse(Console.ReadLine()); while (t-- > 0) { var arrAb = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); // number of places he needs to go var a = arrAb[0]; // number of cab drivers var b = arrAb[0]; var edges = new Edge[a]; for (var i = 0; i < a; i++) { var edgeInput = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); edges[i] = new Edge() {Src = edgeInput[0], Dest = edgeInput[1]}; } // Find the minimum number of edges to connect - Minimum spanning tree var ans = 0; // No need to sort because weights are not holding any value var uf = new UnionFind(b); for (var i = 0; i < a; i++) { var e = edges[i]; if (!uf.IsConnected(e.Src, e.Dest)) { ans++; uf.Union(e.Src, e.Dest); } } Console.WriteLine(ans); } } } }
1 3 3 1 2 2 3 1 3
Show compiler warnings
[
-
]
Show input
Compilation time: 0,58 sec, absolute running time: 0,11 sec, cpu time: 0,14 sec, average memory usage: 18 Mb, average nr of threads: 3, absolute service time: 0,73 sec
edit mode
|
history
2