HackerRank Alex vs Fedor Problem Solution

HackerRank Alex vs Fedor Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Alex vs Fedor Problem Solution.

In order to entertain themselves during the long flight. Alex and Fedor invented the following very simple two players game. The game is:

  • First, Alex draws some graph with bidirectional weighted edges. There are possibly multiple edges (probably, with different or same weights) in this graph.
  • Then Fedor picks some spanning tree of this graph. If the tree appears to be the minimal spanning tree, then the winner is Fedor. Otherwise, the winner is Alex.

We consider two trees different if the sets of the numbers of edges that are included in these trees are different. We consider two sets A and B different if there is at least one element that is present in A and not present in B or vice versa.
We should also mention that the graphs with enormous number of spanning trees upset Alex, as well as Fedor, so they will never have a graph that has more than 1018 spanning trees.
At some point, Fedor became too lazy to look for minimal spanning trees and now he just picks some arbitrary spanning tree from the Alex’s graph. Each spanning tree has equal probability to be picked by Fedor. What is the probability of Fedor’s victory now?

Input Format
The first line of input consists of two single space separated integers N and M – the number of nodes in Alex’s graph and the number of edges in that graph, respectively.
Then there are M lines, where the ith line has three numbers Xi, Yi, Zi, with the meaning that the edge with the number i connects the nodes Xi, and Yi, and has the weight of Zi.

Output Format

Output the probability of Fedor’s victory, if he picks the spanning tree randomly, as an irreducible fraction.

Sample Input

4 4
1 2 1
2 3 4
3 4 3
4 1 2

Sample Output

1/4

Alex vs Fedor C Solution

/*
4 4
1 2 1
2 3 4
3 4 3
4 1 2

1/4
*/

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000000000000003LL
//#define MOD 1500000000000000041LL
unsigned long long CC(unsigned long long n, unsigned long long d);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
void lu(long long **a,long long **ml,long long **mu,long long **dl,long long **du, int n);
long long det(long long **a,int n);
unsigned long long MST();
void dfs(int x,int p);
long long modInverse(long long a,long long mod);
long long mul(unsigned long long x,unsigned long long y);
int N,M,mmst[100][100];
int *u,*v,*w;
long long aa[100][100][100][2];
int map[100];

int main(){
  int i,j,k,c=0;
  long long mst,tst,tmst,C,min;
  long long **a;
  scanf("%d%d",&N,&M);
  u=(int*)malloc(M*sizeof(int));
  v=(int*)malloc(M*sizeof(int));
  w=(int*)malloc(M*sizeof(int));
  a=(long long **)malloc(N*sizeof(long long *));
  for(i=0;i<N;i++)
    a[i]=(long long *)malloc(N*sizeof(long long));
  for(i=0;i<M;i++)
    scanf("%d%d%d",u+i,v+i,w+i);
  for(i=0;i<100;i++)
    map[i]=-1;
  for(i=0;i<M;i++){
    if(map[u[i]-1]==-1)
      map[u[i]-1]=++c;
    if(map[v[i]-1]==-1)
      map[v[i]-1]=++c;
    u[i]=map[u[i]-1];
    v[i]=map[v[i]-1];
  }
  sort_a3(w,u,v,M);
  mst=MST();
  for(i=0;i<N-1;i++)
    for(j=0;j<N-1;j++)
      a[i][j]=0;
  for(i=0;i<M;i++){
    if(u[i]!=N)
      a[u[i]-1][u[i]-1]++;
    if(v[i]!=N)
      a[v[i]-1][v[i]-1]++;
    if(u[i]!=N && v[i]!=N){
      a[u[i]-1][v[i]-1]--;
      a[v[i]-1][u[i]-1]--;
    }
  }
  tst=det(a,N-1);
  for(i=0;i<N-1;i++)
    for(j=0;j<N-1;j++)
      for(k=0;k<M;k++){
        aa[i][j][k][0]=-1;
        aa[i][j][k][1]=0;
      }
  for(i=0;i<M;i++){
    if(u[i]!=N)
      for(j=0;j<M;j++)
        if(aa[u[i]-1][u[i]-1][j][0]==-1 || aa[u[i]-1][u[i]-1][j][0]==w[i]){
          aa[u[i]-1][u[i]-1][j][0]=w[i];
          aa[u[i]-1][u[i]-1][j][1]++;
          break;
        }
    if(v[i]!=N)
      for(j=0;j<M;j++)
        if(aa[v[i]-1][v[i]-1][j][0]==-1 || aa[v[i]-1][v[i]-1][j][0]==w[i]){
          aa[v[i]-1][v[i]-1][j][0]=w[i];
          aa[v[i]-1][v[i]-1][j][1]++;
          break;
        }
    if(u[i]!=N && v[i]!=N){
      for(j=0;j<M;j++)
        if(aa[u[i]-1][v[i]-1][j][0]==-1 || aa[u[i]-1][v[i]-1][j][0]==w[i]){
          aa[u[i]-1][v[i]-1][j][0]=w[i];
          aa[u[i]-1][v[i]-1][j][1]--;
          break;
        }
      for(j=0;j<M;j++)
        if(aa[v[i]-1][u[i]-1][j][0]==-1 || aa[v[i]-1][u[i]-1][j][0]==w[i]){
          aa[v[i]-1][u[i]-1][j][0]=w[i];
          aa[v[i]-1][u[i]-1][j][1]--;
          break;
        }
    }
  }
  dfs(N-1,-1);
  for(j=0;j<N-1;j++){
    min=-1;
    for(i=0;i<N-1;i++)
      for(k=0;k<M && aa[i][j][k][0]!=-1;k++)
        if((min==-1 || aa[i][j][k][0]<min) && aa[i][j][k][1])
          min=aa[i][j][k][0];
    for(i=0;i<N-1;i++){
      a[i][j]=0;
      for(k=0;k<M && aa[i][j][k][0]!=-1;k++)
        if(aa[i][j][k][0]==min){
          a[i][j]=aa[i][j][k][1];
          break;
        }
    }
  }
  tmst=det(a,N-1);
  C=CC(tst,tmst);
  printf("%lld/%lld",tmst/C,tst/C);
  return 0;
}
unsigned long long CC(unsigned long long n, unsigned long long d){
    while( 1 )
    {
        n = n % d;
    if( n == 0 )
        return d;
    d = d % n;
        if( d == 0 )
        return n;
    }
}
void sort_a3(int*a,int*b,int*c,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
    right_c[i]=c[i+m];
  }
  sort_a3(left_a,left_b,left_c,m);
  sort_a3(right_a,right_b,right_c,size-m);
  merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  free(left_c);
  free(right_c);
  return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    }
  }
  return;
}
void lu(long long **a,long long **ml,long long **mu,long long **dl,long long **du, int n){
    int i = 0, j = 0, k = 0;
    long long t1,t2;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (j < i){
                ml[j][i] = 0;
                dl[j][i] = 1;
            }
            else
            {
                //l[j][i] = (a[j][i]+MOD)%MOD;
                ml[j][i] = a[j][i];
                dl[j][i] = 1;

                for (k = 0; k < i; k++)
                {
                    //l[j][i] = (l[j][i] - l[j][k] * u[k][i]%MOD+MOD)%MOD;   l[j][i] = l[j][i] - l[j][k] * u[k][i];
                    t1=mul(ml[j][k] , mu[k][i]);
                    t2=mul(dl[j][k] , du[k][i]);
                    ml[j][i]=(mul(ml[j][i],t2)-mul(t1,dl[j][i])+MOD)%MOD;
                    dl[j][i]=mul(dl[j][i],t2);

                }
            }
        }
        for (j = 0; j < n; j++)
        {
            if (j < i){
                mu[i][j] = 0;
                du[i][j] = 1;
            }
            else if (j == i){
                mu[i][j] = 1;
                du[i][j] = 1;
            }
            else
            {
                //u[i][j] = (a[i][j]+MOD)%MOD * modInverse(l[i][i],MOD)%MOD;  u[i][j] = a[i][j] / l[i][i];
                mu[i][j]=mul(a[i][j],dl[i][i]);
                du[i][j]=ml[i][i];

                for (k = 0; k < i; k++)
                {
                    //u[i][j] = (u[i][j] - ((l[i][k] * u[k][j]%MOD) * modInverse(l[i][i],MOD)%MOD)+MOD)%MOD;   u[i][j] = u[i][j] - ((l[i][k] * u[k][j]) / l[i][i]);
                    t1=mul(mul(ml[i][k] , mu[k][j]),dl[i][i]);
                    t2=mul(mul(dl[i][k] , du[k][j]),ml[i][i]);
                    mu[i][j]=(mul(mu[i][j],t2)-mul(t1,du[i][j])+MOD)%MOD;
                    du[i][j]=mul(du[i][j],t2);
                    
                    
                    
                }
            }
        }
    }
}
long long det(long long **a,int n){
  long long **ml,**mu,**dl,**du,ans=1;
  int i,j;
  ml=(long long **)malloc(n*sizeof(long long *));
  for(i=0;i<n;i++)
    ml[i]=(long long *)malloc(n*sizeof(long long));
  mu=(long long **)malloc(n*sizeof(long long *));
  for(i=0;i<n;i++)
    mu[i]=(long long *)malloc(n*sizeof(long long));
  dl=(long long **)malloc(n*sizeof(long long *));
  for(i=0;i<n;i++)
    dl[i]=(long long *)malloc(n*sizeof(long long));
  du=(long long **)malloc(n*sizeof(long long *));
  for(i=0;i<n;i++)
    du[i]=(long long *)malloc(n*sizeof(long long));
  for(i=0;i<n;i++)
    for(j=0;j<n;j++){
      ml[i][j]=mu[i][j]=0;
      dl[i][j]=du[i][j]=1;
      a[i][j]=(a[i][j]+MOD)%MOD;
    }
  lu(a,ml,mu,dl,du,n);
  for(i=0;i<n;i++)
    ans=mul(mul(ans,ml[i][i]),modInverse(dl[i][i],MOD));
  for(i=0;i<n;i++){
    free(ml[i]);
    free(mu[i]);
    free(dl[i]);
    free(du[i]);
  }
  free(ml);
  free(mu);
  free(dl);
  free(du);
  return ans;
}
unsigned long long MST(){
  unsigned long long ans=0;
  int i,j,p1,p2,p3,p4;
  for(i=0;i<N;i++)
    for(j=0;j<N;j++)
      mmst[i][j]=0;
  int *p=(int*)malloc(N*sizeof(int));
  for(i=0;i<N;i++)
    p[i]=i;
  for(i=0;i<M;i++){
    p1=u[i]-1;
    while(p[p1]!=p1)
      p1=p[p1];
    p2=v[i]-1;
    while(p[p2]!=p2)
      p2=p[p2];
    if(p1!=p2){
      ans=ans+w[i];
      mmst[u[i]-1][v[i]-1]=1;
      mmst[v[i]-1][u[i]-1]=1;
    }
    p3=u[i]-1;
    while(1){
      if(p[p3]==p3){
        p[p3]=p1;
        break;
      }
      p4=p3;
      p3=p[p3];
      p[p4]=p1;
    }
    p3=v[i]-1;
    while(1){
      if(p[p3]==p3){
        p[p3]=p1;
        break;
      }
      p4=p3;
      p3=p[p3];
      p[p4]=p1;
    }
  }
  free(p);
  return ans;
}
void dfs(int x,int p){
  int i,j,k;
  for(i=0;i<N;i++)
    if(mmst[x][i] && i!=p)
      dfs(i,x);
  if(p!=-1 && p!=N-1)
    for(i=0;i<N-1;i++)
      for(j=0;j<N-1 && aa[i][x][j][0]!=-1;j++)
        for(k=0;k<M;k++)
          if(aa[i][p][k][0]==-1 || aa[i][p][k][0]==aa[i][x][j][0]){
            aa[i][p][k][0]=aa[i][x][j][0];
            aa[i][p][k][1]+=aa[i][x][j][1];
            break;
          }
  return;
}
long long modInverse(long long a,long long mod){
    long long b0 = mod, t, q;
    long long x0 = 0, x1 = 1;
    while (a > 1) {
        q = a / mod;
        t = mod; mod = a % mod; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += b0;
    return x1;
}
long long mul(unsigned long long x,unsigned long long y){
  unsigned long long a,b,c,d,A,B,C;
  long long ans;
  int i;
  a=x/1000000000;
  b=x%1000000000;
  c=y/1000000000;
  d=y%1000000000;
  A=d*b%MOD;
  B=(d*a+c*b)%MOD;
  C=a*c%MOD;
  for(i=0;i<9;i++)
    B=B*10%MOD;
  for(i=0;i<18;i++)
    C=C*10%MOD;
  ans=(A+B+C)%MOD;
  return ans;
}

Alex vs Fedor C++ Solution

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <bitset>
#include <queue>
#include <map>
#include <set>

using namespace std;

// Self Template Code BGEIN

#define sz(x) ((int)((x).size()))
#define out(x) printf(#x" %d\n", x)
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repf(i,a,b) for (int i = (a); i <= (b); ++i)
#define repd(i,a,b) for (int i = (a); i >= (b); --i)
#define repcase int t, Case = 1; for (scanf ("%d", &t); t; --t)
#define repeach(i,x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i)

typedef long long int64;
typedef pair<int, int> pii;

int sgn(double x) { return (x > 1e-8) - (x < -1e-8); }
int count_bit(int x) { return x == 0? 0 : count_bit(x >> 1) + (x & 1); }

template<class T> inline void ckmin(T &a, const T b) { if (b < a) a = b; }
template<class T> inline void ckmax(T &a, const T b) { if (b > a) a = b; }

// Self Template Code END

const int MAXN = 100 + 10;

struct edge_node {
    int u, v, w;

    void input() {
        scanf ("%d%d%d", &u, &v, &w);
        --u, --v;
    }
    bool operator<(const edge_node& rhs) const {
        return w < rhs.w;
    }
};

struct disjoint_set {
    int p[MAXN];

    void clear(int n) { rep (i, n) p[i] = i; }
    int find(int x) { return x == p[x]? x : p[x] = find(p[x]); }
    bool join(int x, int y) { x = find(x), y = find(y); return x == y? false : p[x] = y, true; }

} ds, ds_tmp;

edge_node edges[MAXN];
int tmp_gcnt[MAXN][MAXN];
bool vis[MAXN];
int n, m;

int64 get_det(int64 a[][MAXN], int n) {
    // Gauss -> get det(a[1:][1:])
    int64 ret = 1;
    // Ignore the first row and column
    repf (i, 1, n - 1) {
        repf (j, i + 1, n - 1) {
            // like gcd with eculid: mod and swap
            while (a[j][i]) {
                int64 t = a[i][i] / a[j][i];
                repf (k, i, n - 1) a[i][k] -= a[j][k] * t;
                repf (k, i, n - 1) swap (a[i][k], a[j][k]);
                ret = -ret;
            }
        }
        if (a[i][i] == 0) return 0;
        ret *= a[i][i];
    }
    return abs(ret);
}

void add_edge_to_kmat(int64 a[][MAXN], int x, int y, int cnt = 1) {
    a[x][x] += cnt; a[y][y] += cnt;
    a[x][y] -= cnt; a[y][x] -= cnt;
}

int64 get_mst_cnt_one_block() {
    map<int, vector<int> > blocks;
    rep (i, n) if (vis[i]) {
        vis[i] = false;
        blocks[ds_tmp.find(i)].push_back(i);
    }

    int64 ret = 1;
    for (const auto& block : blocks) {
        if (sz(block.second) <= 1) {
            continue ;
        }

        // calc current Kirchhoff matrix
        int len = sz(block.second);
        int64 kmat[MAXN][MAXN] = {0};
        rep (x, len) rep (y, x) {
            add_edge_to_kmat(kmat, x, y, tmp_gcnt[block.second[x]][block.second[y]]);
        }
        ret *= get_det(kmat, len);

        // link all points in the block to the root
        rep (x, len) {
            ds.p[block.second[x]] = block.first;
        }
    }

    // sync ds_tmp with ds
    rep (i, n) {
        ds.p[i] = ds_tmp.p[i] = ds.find(i);
    }
    return ret;
}

int64 get_mst_cnt() {
    sort (edges, edges + m);
    ds.clear(n), ds_tmp.clear(n);
    memset (vis, 0, sizeof(vis));
    memset (tmp_gcnt, 0, sizeof(tmp_gcnt));

    int pre_e_len = -1;
    int64 ret = 1;
    rep (i, m) {
        if (pre_e_len != edges[i].w) {
            ret *= get_mst_cnt_one_block();
            pre_e_len = edges[i].w;
        }
        int pu = ds.find(edges[i].u), pv = ds.find(edges[i].v);
        if (pu == pv) {
            continue;
        }
        vis[pu] = vis[pv] = true;
        ds_tmp.join(pu, pv);
        tmp_gcnt[pu][pv] += 1;
        tmp_gcnt[pv][pu] += 1;
    }
    return ret * get_mst_cnt_one_block();
}

int64 get_st_cnt() {
    // Kirchhoff matrix
    int64 kmat[MAXN][MAXN] = {0};
    rep (i, m) {
        add_edge_to_kmat(kmat, edges[i].u, edges[i].v);
    }
    return get_det(kmat, n);
}

int main() {
    while (scanf ("%d%d", &n, &m) != EOF) {
        rep (i, m) {
            edges[i].input();
        }
        int64 mst_cnt = get_mst_cnt();
        int64 st_cnt = get_st_cnt();
        int64 gcd_ab = __gcd(mst_cnt, st_cnt);
        // gcd_ab = 1;
        cout << mst_cnt / gcd_ab << '/' << st_cnt / gcd_ab << endl;
    }
    return 0;
}

Alex vs Fedor C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'alexFedor' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts WEIGHTED_INTEGER_GRAPH graph as parameter.
     */

    /*
     * For the weighted graph, <name>:
     *
     * 1. The number of nodes is <name>Nodes.
     * 2. The number of edges is <name>Edges.
     * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i].
     *
     */
        public static string alexFedor(int graphNodes, List<int> graphFrom, List<int> graphTo, List<int> graphWeight)
        {
            var graph = new Graph(graphNodes, graphFrom, graphTo, graphWeight);
            var mst = Kruskal(graph);
            var m = mst.Item2;
            var n = Kirchoff(graph);
            var gcd = GreatestCommonDivisor(m, n);

            return $"{m / gcd}/{n / gcd}";
        }

        public struct Graph
        {
            public Graph(int vertexCount, List<int> fromVertexes, List<int> toVertexes, List<int> weights)
            {
                VertexCount = vertexCount;
                Edges = fromVertexes.Zip(toVertexes, (u, v) => new { u, v }).Where(e => e.u != e.v).Zip(weights, (e, w) => new Edge(e.u - 1, e.v - 1, w)).ToArray();
            }

            public int VertexCount;
            public Edge[] Edges;
        }

        public struct Edge : IComparable
        {
            public Edge(int u, int v, int weight) { U = u; V = v; Weight = weight; }

            public int U;
            public int V;
            public int Weight;

            public int CompareTo(object obj) => Weight.CompareTo(((Edge)obj).Weight);
        }

        public static (List<Edge>, long) Kruskal(Graph graph)
        {
            var mst = new List<Edge>(graph.VertexCount - 1);
            var m = 1L;
            int w = -1;
            var parents = Enumerable.Range(0, graph.VertexCount).Select(v => v).ToArray();

            Array.Sort(graph.Edges);

            for (int i = 0; i < graph.Edges.Length; i++)
            {
                var u = Find(parents, graph.Edges[i].U);
                var v = Find(parents, graph.Edges[i].V);

                if (u != v)
                {
                    if (w < graph.Edges[i].Weight)
                    {
                        w = graph.Edges[i].Weight;
                        var edges = graph.Edges.Skip(i).TakeWhile(e => e.Weight == w)
                                               .Select(e => new Edge(Find(parents, e.U), Find(parents, e.V), w))
                                               .Where(e => e.U != e.V).ToList();

                        if (edges.Count > 1)
                        {
                            foreach (var g in GetConnectedComponents(edges))
                            {
                                m *= Kirchoff(g);
                            }
                        }
                    }

                    mst.Add(graph.Edges[i]);
                    Union(parents, u, v);

                    if (mst.Count == mst.Capacity)
                    {
                        return (mst, m);
                    }
                }
            }

            return (new List<Edge>(), 0);
        }

        private static int Find(int[] parents, int v) => v == parents[v] ? v : Find(parents, parents[v]);

        private static IEnumerable<Graph> GetConnectedComponents(List<Edge> edges)
        {
            while (edges.Any())
            {
                var vertexes = GetConnectedVertexesReindexed(edges, edges[0].U);
                var groups = edges.GroupBy(e => vertexes.ContainsKey(e.U) || vertexes.ContainsKey(e.V));

                if (vertexes.Count > 1)
                {
                    yield return new Graph()
                    {
                        VertexCount = vertexes.Count,
                        Edges = groups.Single(g => g.Key).Select(e => new Edge(vertexes[e.U], vertexes[e.V], e.Weight)).ToArray()
                    };
                }

                edges = groups.SingleOrDefault(g => !g.Key)?.ToList() ?? new List<Edge>();
            }
        }

        public static Dictionary<int, int> GetConnectedVertexesReindexed(List<Edge> edges, int start)
        {
            var vertexes = new Dictionary<int, int>();
            var stack = new Stack<int>(new[] { start });

            while (stack.Count > 0)
            {
                var u = stack.Pop();

                if (vertexes.ContainsKey(u))
                    continue;

                vertexes.Add(u, vertexes.Count);

                foreach (var v in edges.Where(e => e.U == u || e.V == u))
                {
                    stack.Push(v.U == u ? v.V : v.U);
                }
            }

            return vertexes;
        }

        private static void Union(int[] parents, int u, int v) => parents[u] = parents[v];

        public static long Kirchoff(Graph graph)
        {
            var qp = GetAdjacencyMatrix(graph, 1);
            return Determinant(qp);
        }

        private static int[,] GetAdjacencyMatrix(Graph graph, int skip)
        {
            var n = graph.VertexCount - skip;
            var matrix = new int[n, n];

            for (int i = 0; i < graph.Edges.Length; i++)
            {
                var u = graph.Edges[i].U - skip;
                var v = graph.Edges[i].V - skip;

                if (u >= 0)
                {
                    matrix[u, u]++;

                    if (v >= 0)
                    {
                        matrix[v, v]++;
                        matrix[u, v]--;
                        matrix[v, u]--;
                    }
                }
                else if (v >= 0)
                {
                    matrix[v, v]++;
                }
            }

            return matrix;
        }

        private static long Determinant(int[,] matrix)
        {
            var n = matrix.GetLength(0);
            var lu = DecomposeLU(matrix);
            var d = lu[0, 0];

            for (int i = 1; i < n; i++)
            {
                d *= lu[i, i];
            }

            return Convert.ToInt64(Math.Round(d, 18));
        }

        private static decimal[,] DecomposeLU(int[,] matrix)
        {
            var n = matrix.GetLength(0);
            var lu = new decimal[n, n];

            for (int i = 0; i < n; i++)
            {
                for (int j = i; j < n; j++)
                {
                    decimal sum = 0;

                    for (int k = 0; k < i; k++)
                    {
                        sum += lu[i, k] * lu[k, j];
                    }

                    lu[i, j] = matrix[i, j] - sum;
                }

                for (int j = i + 1; j < n; j++)
                {
                    decimal sum = 0;

                    for (int k = 0; k < i; k++)
                    {
                        sum += lu[j, k] * lu[k, i];
                    }

                    lu[j, i] = (1 / lu[i, i]) * (matrix[j, i] - sum);
                }
            }

            return lu;
        }
        private static long GreatestCommonDivisor(long a, long b)
        {
            while (a != 0 && b != 0)
            {
                if (a > b)
                    a %= b;
                else
                    b %= a;
            }

            return a | b;
        }
}

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

        string[] graphNodesEdges = Console.ReadLine().TrimEnd().Split(' ');

        int graphNodes = Convert.ToInt32(graphNodesEdges[0]);
        int graphEdges = Convert.ToInt32(graphNodesEdges[1]);

        List<int> graphFrom = new List<int>();
        List<int> graphTo = new List<int>();
        List<int> graphWeight = new List<int>();

        for (int i = 0; i < graphEdges; i++)
        {
            string[] graphFromToWeight = Console.ReadLine().TrimEnd().Split(' ');

            graphFrom.Add(Convert.ToInt32(graphFromToWeight[0]));
            graphTo.Add(Convert.ToInt32(graphFromToWeight[1]));
            graphWeight.Add(Convert.ToInt32(graphFromToWeight[2]));
        }

        string result = Result.alexFedor(graphNodes, graphFrom, graphTo, graphWeight);

        textWriter.WriteLine(result);

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

Alex vs Fedor Java Solution

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Solution {

  static class EdgeNode implements Comparable<EdgeNode> {
    int u;
    int v;
    int w;

    EdgeNode(int u, int v, int w) {
      this.u = u;
      this.v = v;
      this.w = w;
    }

    @Override
    public int compareTo(EdgeNode rhs) {
      return w - rhs.w;
    }
  }

  static class DisjointSet {
    int[] p;
    
    DisjointSet(int n) {
      p = new int[n];
    }

    void clear() {
      for (int i = 0; i < p.length; i++) {
        p[i] = i;
      }
    }
    
    int find(int x) {
      if (x == p[x]) {
        return x;
      }
      return p[x] = find(p[x]);
    }

    boolean join(int x, int y) {
      x = find(x);
      y = find(y);
      if (x == y) {
        return false;
      }
      p[x] = y;
      return  true;
    }

  }
  
  static long getDet(long[][] a, int n) {
    long ret = 1;
    for (int i = 1; i <= n - 1; i++) {
      for (int j = i + 1; j <= n - 1; j++) {
        while (a[j][i] != 0) {
          long t = a[i][i] / a[j][i];
          for (int k = i; k <= n - 1; k++) {
            a[i][k] -= a[j][k] * t;
          }
          for (int k = i; k <= n - 1; k++) {
            long tmp = a[i][k];
            a[i][k] = a[j][k];
            a[j][k] = tmp;
          }
          ret = -ret;
        }
      }
      if (a[i][i] == 0) {
        return 0;
      }
      ret *= a[i][i];
    }
    return Math.abs(ret);
  }

  static void addEdgeToKmat(long[][] a, int x, int y) {
    addEdgeToKmat(a, x, y, 1);
  }

  static void addEdgeToKmat(long[][] a, int x, int y, int cnt) {
    a[x][x] += cnt;
    a[y][y] += cnt;
    a[x][y] -= cnt;
    a[y][x] -= cnt;
  }

  static int[][] tmpGcnt;
  static DisjointSet ds;
  static DisjointSet dsTmp;
  static boolean[] vis;
  
  static long getMstCntOneBlock() {
    Map<Integer, List<Integer> > blocks = new HashMap<>();
    for (int i = 0; i < vis.length; i++) {
      if (vis[i]) {
        vis[i] = false;
        int index = dsTmp.find(i);
        List<Integer> l = blocks.get(index);
        if (l == null) {
          l = new ArrayList<>();
          blocks.put(index, l);
        }
        l.add(i);
      }
    }

    long ret = 1;
    for (Map.Entry<Integer, List<Integer>> block : blocks.entrySet()) {
      int len = block.getValue().size();
      if (len <= 1) {
        continue ;
      }
      List<Integer> l = block.getValue();

      long[][] kmat = new long [tmpGcnt.length][tmpGcnt.length];
      
      for (int x = 0; x < len; x++) {
        for (int y = 0; y < x; y++) {
          addEdgeToKmat(kmat, x, y, tmpGcnt[l.get(x)][l.get(y)]);
        }
      }
      ret *= getDet(kmat, len);

      for (int x = 0; x < len; x++) {
        ds.p[l.get(x)] = block.getKey();
      }
    }

    for (int i = 0; i < ds.p.length; i++) {
      ds.p[i] = dsTmp.p[i] = ds.find(i);
    }
    return ret;
  }

  static long getMstCnt(EdgeNode[] edges) {
    Arrays.sort(edges);
    ds.clear();
    dsTmp.clear();
    Arrays.fill(vis, false);
    for (int[] arr : tmpGcnt) {
      Arrays.fill(arr, 0);
    }

    int preELen = -1;
    long ret = 1;
    for (int i = 0; i < edges.length; i++) {
      if (preELen != edges[i].w) {
        ret *= getMstCntOneBlock();
        preELen = edges[i].w;
      }
      int pu = ds.find(edges[i].u);
      int pv = ds.find(edges[i].v);
      if (pu == pv) {
        continue;
      }
      vis[pu] = vis[pv] = true;
      dsTmp.join(pu, pv);
      tmpGcnt[pu][pv] += 1;
      tmpGcnt[pv][pu] += 1;
    }
    return ret * getMstCntOneBlock();
  }
  
  static long getStCnt(EdgeNode[] edges, int n) {
    long[][] kmat = new long[n][n];
    for (int i = 0; i < edges.length; i++) {
      addEdgeToKmat(kmat, edges[i].u, edges[i].v);
    }
    return getDet(kmat, n);
  }


  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int graphNodes = Integer.parseInt(st.nextToken());
    int graphEdges = Integer.parseInt(st.nextToken());

    EdgeNode[] edges = new EdgeNode[graphEdges];    
    for (int i = 0; i < graphEdges; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken())-1;
      int v = Integer.parseInt(st.nextToken())-1;
      int w = Integer.parseInt(st.nextToken());
      edges[i] = new EdgeNode(u, v, w);
    }

    vis = new boolean[graphNodes];
    ds = new DisjointSet(graphNodes);
    dsTmp = new DisjointSet(graphNodes);
    tmpGcnt = new int[graphNodes][graphNodes];
    
    long mstCnt = getMstCnt(edges);
    long stCnt = getStCnt(edges, graphNodes);
    if (mstCnt == stCnt) {
      bw.write("1/1");
    } else {
      long gcdAb = BigInteger.valueOf(mstCnt).gcd(BigInteger.valueOf(stCnt)).intValue();
      bw.write((mstCnt / gcdAb) + "/" + (stCnt / gcdAb));
    }
    bw.newLine();

    bw.close();
    br.close();
  }
}

Alex vs Fedor Python Solution

import os
import sys
from decimal import *

#
# Complete the alexFedor function below.
#

#
# For the weighted graph, <name>:
#
# 1. The number of nodes is <name>_nodes.
# 2. The number of edges is <name>_edges.
# 3. An edge exists between <name>_from[i] to <name>_to[i] and the weight of the edge is <name>_weight[i].
#
#
def alexFedor(graph_nodes, graph_from, graph_to, graph_weight):
    #
    # Write your code here.
    #
    getcontext().prec = 30

    def gcd(x, y):
        return gcd(y, x % y) if y else x

    def find(x):
        if x != pre[x]:
            pre[x] = find(pre[x])
        return pre[x]

    def join(_x, _y):
        pre[find(_x)] = find(_y)

    def gauss(n0):
        if n0 <= 1:
            return 1
        n0 -= 1
        res = 1
        d = [[0]*n0 for _ in range(n0)]
        for i in range(n0):
            for j in range(n0):
                d[i][j] = Decimal(a[i][j])
        for i in range(n0):
            if d[i][i] == 0:
                for j in range(i+1, n0):
                    if d[j][i] != 0:
                        for k in range(i,n0):
                            d[i][k], d[j][k] = d[j][k], d[i][k]
                        break
            for j in range(i+1, n0):
                tmp = d[j][i]
                for k in range(n0):
                    d[j][k] -= d[i][k] / d[i][i] * tmp
            res *= d[i][i]
        return int(abs(res)+Decimal(0.5))

    graph_from = [x-1 for x in graph_from]
    graph_to = [x-1 for x in graph_to]
    n, m = graph_nodes, len(graph_from)
    #a = ([[0] * n]) * n
    a = [[0] * n for _ in range(n)]
    for i in range(m):
        x, y = graph_from[i], graph_to[i]
        a[x][x] += 1
        a[y][y] += 1
        a[x][y] -= 1
        a[y][x] -= 1
    al_count = gauss(n)
    min_count = 1
    idx = list(range(m))
    pre = list(range(n))
    idx.sort(key=lambda _x: graph_weight[_x])
    l = 0
    while l < m:
        r = l + 1
        while r < m and graph_weight[idx[l]] == graph_weight[idx[r]]:
            r += 1
        for i in range(l, r):
            graph_from[idx[i]] = find(graph_from[idx[i]])
            graph_to[idx[i]] = find(graph_to[idx[i]])
        for i in range(l, r):
            join(graph_from[idx[i]], graph_to[idx[i]])
        idx[l:r] = sorted(idx[l:r], key=lambda _x: find(graph_from[_x]))
        ll = l
        while ll < r:
            rr = ll + 1
            while rr < r and find(graph_from[idx[ll]]) == find(graph_from[idx[rr]]):
                rr += 1
            # calculate ways with pathes id from ll to rr
            v = [0] * n
            for i in range(ll, rr):
                v[graph_from[idx[i]]] = v[graph_to[idx[i]]] = 1
            for i in range(1, n):
                v[i] += v[i-1]
            for i in range(v[-1]):
                for j in range(v[-1]):
                    a[i][j] = 0
            for i in range(ll, rr):
                x, y = v[graph_from[idx[i]]] - 1, v[graph_to[idx[i]]] - 1
                a[x][x] += 1
                a[y][y] += 1
                a[x][y] -= 1
                a[y][x] -= 1
            min_count *= gauss(v[-1])
            ll = rr
        l = r
    for i in range(1, n):
        if find(i) != find(0):
            min_count = 0
    _gcd = gcd(al_count, min_count)
    if _gcd:
        al_count //= _gcd
        min_count //= _gcd
    return str(min_count) + '/' + str(al_count)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    graph_nodes, graph_edges = map(int, input().split())

    graph_from = [0] * graph_edges
    graph_to = [0] * graph_edges
    graph_weight = [0] * graph_edges

    for graph_itr in range(graph_edges):
        graph_from[graph_itr], graph_to[graph_itr], graph_weight[graph_itr] = map(int, input().split())

    result = alexFedor(graph_nodes, graph_from, graph_to, graph_weight)

    fptr.write(result + '\n')

    fptr.close()
c C# C++ java javascript python