HackerRank: World codesprint #4 - Roads in HackerLand - C# code to study - II

RoadsInHackerLand2.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        new Roads_in_HackerLand().Solve();
    }
}

class Roads_in_HackerLand
{
	public void Solve()
	{
		var z = Console.In.ReadToEnd()
			.Split(new char[] { ' ', '\t', '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)
			.Select(_s => int.Parse(_s)).ToArray();
		var n = z[0];
		var m = z[1];
		var a = new int[m];
		var b = new int[m];
		var c = new int[m];
		var o = new int[m];

		for (int i = 2, j = 0; j < m; i += 3, ++j)
		{
			a[j] = z[i] - 1;
			b[j] = z[i + 1] - 1;
			c[j] = z[i + 2];
		}

		for (var i = 0; i < m; ++i)
		{
			o[c[i]] = i;
		}

		var p = new int[n];
		var r = new int[n];
		var t = new int[n - 1];

		for (var i = 0; i < n; ++i)
		{
			p[i] = i;
		}

		for (int i = 0, j = 0; i < o.Length; ++i)
		{
			var u = a[o[i]]; for (; u != p[u]; u = p[u]) ;
			var v = b[o[i]]; for (; v != p[v]; v = p[v]) ;

			if (u != v)
			{
				t[j++] = o[i];

				if (r[u] < r[v])
				{
					p[u] = v;
				}
				else
				{
					p[v] = u;

					if (r[u] == r[v])
					{
						++r[u];
					}
				}
			}
		}

		var d = new int[n];
		var e = new int[n];
		var g = new int[2 * n];
		var h = new int[n];

		for (var i = 0; i < n - 1; ++i)
		{
			var u = a[t[i]];
			var v = b[t[i]];

			++d[u];
			++d[v];
			++h[u];
			++h[v];
		}

		for (var u = 0; u < n; ++u)
		{
			e[u] = 1;
		}

		for (var u = 1; u < n; ++u)
		{
			h[u] += h[u - 1];
		}

		var f = (int[])h.Clone();

		for (var i = 0; i < n - 1; ++i)
		{
			var u = a[t[i]];
			var v = b[t[i]];

			g[--f[u]] = v;
			g[--f[v]] = u;
		}

		var w = new int[n];
		var ff = new bool[n];
		var f_i = 1;

		ff[0] = true;
		f[0] = 0;
		w[0] = -1;

		while (f_i > 0)
		{
			var u = f[--f_i];
			var i = u == 0 ? 0 : h[u - 1];
			var j = h[u];

			for (; i < j; ++i)
			{
				if (!ff[g[i]])
				{
					ff[g[i]] = true;
					f[f_i++] = g[i];
					w[g[i]] = u;
				}
			}
		}

		for (var u = 0; u < n; ++u)
		{
			for (var v = u; v != 0 && d[v] == 1; v = w[v])
			{
				--d[v];
				--d[w[v]];
				e[w[v]] += e[v];
			}
		}

		var k = 0;
		var s = 0L;
		var x_n = 0;
		var x = new int[2 * m];

		for (var i = 0; i < n - 1; ++i)
		{
			var q = Math.Min(e[a[t[i]]], e[b[t[i]]]);

			for (var j = c[t[i]] - k; --j >= 0; s >>= 1)
			{
				x[x_n++] = (int)s & 1;
			}

			k = c[t[i]];
			s += (long)q * (n - q);
		}

		for (; s > 0; s >>= 1)
		{
			x[x_n++] = (int)s & 1;
		}

		var ic = new char[x_n];

		for (int i = x_n - 1, j = 0; i >= 0; --i, ++j)
		{
			ic[j] = (char)('0' + x[i]);
		}

		Console.WriteLine(new string(ic));
	}
}