HackerRank Jim and his LAN Party problem solution

In this HackerRank Jim and his LAN Party problem solution For each game, find out the wire after adding which the group can start playing. It is also possible that a group will never get connected. In such a case, this group starts crying and you should display -1.

Problem solution in Python.

import sys

def read():
    l = sys.stdin.readline()
    if l[-1] == 'n': l = l[:-1]
    xs = filter(lambda x: len(x) > 0, l.split(' '))
    return map(int, xs)

n, m, q = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
    gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
    uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
    if len(gs[ix]) < 2:
        res.append(0)
    else:
        res.append(-1)

def find(x):
    if uf[x][0] == x:
        return x
    r = find(uf[x][0])
    uf[x][0] = r
    return r

def union(u, v, ix):
    ur = find(u)
    vr = find(v)
    ur, uh, us = uf[ur]
    vr, vh, vs = uf[vr]
    if uh > vh:
        uf[vr][0] = ur
        uf[ur][2] |= vs
        for g in vs:
            gs[g].discard(vr)
            gs[g].add(ur)
            if res[g] < 0 and len(gs[g]) == 1:
                res[g] = ix + 1
    elif vh > uh:
        uf[ur][0] = vr
        uf[vr][2] |= us
        for g in vs:
            gs[g].discard(ur)
            gs[g].add(vr)
            if res[g] < 0 and len(gs[g]) == 1:
                res[g] = ix + 1
    else:
        uf[vr][0] = ur
        uf[ur][1] += 1
        uf[ur][2] |= vs
        for g in vs:
            gs[g].discard(vr)
            gs[g].add(ur)
            if res[g] < 0 and len(gs[g]) == 1:
                res[g] = ix + 1

for ix in range(q):
    u, v = map(lambda x: x - 1, read())
    union(u, v, ix)
for r in res:
    print(r)
    

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
  
  static int find(int[] uf, int x) {
    while (uf[x] != x) {
      uf[x] = uf[uf[x]];
      x = uf[x];
    }
    return x;
  }
  
  static void iota(int v[], int val) {
    for (int i = 0; i < v.length; i++) {
      v[i] = val++;
    }
  }

  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 n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    Map<Integer, Integer>[] a = new HashMap[n];
    int[] cnt = new int[n];
    
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      int item = Integer.parseInt(st.nextToken()) - 1;
      a[i] = new HashMap<>();
      a[i].put(item, 1);
      cnt[item]++;

    }
    int[] result = new int[m];
    Arrays.fill(result, -1);
    for (int i = 0; i < m; i++) {
      if (cnt[i] <= 1) {
        result[i] = 0;
      }
    }
    int[] uf = new int[n];
    iota(uf, 0);
    

    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken())-1;
      int v = Integer.parseInt(st.nextToken())-1;

      int uu = find(uf, u);
      int vv = find(uf, v);
      if (uu != vv) {
        if (a[uu].size() < a[vv].size()) {
          int temp = uu;
          uu = vv;
          vv = temp;
        }
        uf[vv] = uu;
        for (Map.Entry<Integer, Integer> x: a[vv].entrySet()) { 
          int t = a[uu].getOrDefault(x.getKey(), 0) + x.getValue();
          a[uu].put(x.getKey(), t);
          if (t == cnt[x.getKey()] && result[x.getKey()] == -1) {
            result[x.getKey()] = i+1;
          }
        }
      }
    }

    for (int i = 0; i < result.length; i++) {
      bw.write(String.valueOf(result[i]));

      if (i != result.length - 1) {
        bw.write("n");
      }
    }

    bw.newLine();

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

Problem solution in C++.

#include <iostream>
#include <vector>
using namespace std;
#define SZ(x) ( (int) (x).size() )
const int MAX_N = 100000 + 1;
int N, M, Q;
int color[MAX_N];
vector<int> cpos[MAX_N];
vector<int> q[MAX_N];
int qu[MAX_N], qv[MAX_N];
int lo[MAX_N], hi[MAX_N];
// implementation of UFDS
int f[MAX_N];
int getf(int x){
  return f[x] == x ? x : f[x] = getf(f[x]);
}
void mergef(int x, int y){
  f[getf(x)] = getf(y);
}
void initf(){
  for(int i = 1; i <= N; i++){
    f[i] = i;
  }
}

void reloadQueries(){
  for(int i = 0; i <= Q; i++){
    q[i].clear();
  }
  for(int i = 1; i <= M; i++){
    q[(lo[i] + hi[i]) / 2].push_back(i);
  }
}

void answerQuery(int c){
  bool connected = true;
  for(int i = 1; i < (int) cpos[c].size(); i++){
    connected &= getf(cpos[c][i]) == getf(cpos[c][i - 1]);
  }
  int mid = (lo[c] + hi[c]) / 2;
  if(!connected){
    lo[c] = mid + 1;
  } else {
    hi[c] = mid;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin >> N >> M >> Q;
  for(int i = 1; i <= N; i++){
    cin >> color[i];
    cpos[color[i]].push_back(i);
  }
  for(int i = 1; i <= M; i++){
    lo[i] = 0, hi[i] = Q;
  }
  for(int i = 1; i <= Q; i++){
    cin >> qu[i] >> qv[i];
  }
  for(int times = 25; times >= 0; times --){
    initf();
    reloadQueries();
    for(int i = 0; i <= Q; i++){
      if(i > 0)
    mergef(qu[i], qv[i]);
      for(int j = 0; j < SZ(q[i]); j++){
    answerQuery(q[i][j]);
      }
    }
  }
  for(int i = 1; i <= M; i++){
    if(lo[i] > Q){
      cout << -1 << 'n';
    } else {
      cout << lo[i] << 'n';
    }
  }
  return 0;
}

Problem solution in C.

#include<stdio.h>
long findparent(long a, long connected[])
{
    if( connected[a] == a )
    {
        return a;
    }
    return findparent(connected[a], connected);
}
int checkparent(long arr[], long x, long N, long connected[])
{
    long i, val = arr[x], parent = findparent(x, connected);
    for( i = 1 ; i <= N ; i++ )
    {
        if( i != x && arr[i] == val && findparent(i, connected) != parent )
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    long N, M, Q, i, x, y, *arr, *connected, *step, *cnt, *cnt1, *ans, *par;
    scanf("%ld %ld %ld", &N, &M, &Q);
    arr = (long*)malloc(( N + 1 ) * sizeof(long));
    connected = (long*)malloc(( N + 1 ) * sizeof(long));
    memset(connected, 0, (N+1)*sizeof(cnt));
    step = (long*)malloc(( N + 1 ) * sizeof(long));
    memset(step, 0, (N+1)*sizeof(step));
    cnt = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(cnt, 0, (M+1)*sizeof(cnt));
    cnt1 = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(cnt1, 0, (M+1)*sizeof(cnt1));
    ans = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(ans, -1, (M+1)*sizeof(ans));
    par = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(par, -1, (M+1)*sizeof(par));
    for( i = 1 ; i <= N ; i++ )
    {
        scanf("%ld", &arr[i]);
        cnt[arr[i]]++;
    }
    for( i = 1 ; i <= Q ; i++ )
    {
        scanf("%ld %ld", &x, &y);
        if( connected[x] == 0 && connected[y] == 0 )
        {
            if( x < y )
            {
                connected[x] = x;
                connected[y] = x;
                par[arr[x]] = x;
                par[arr[y]] = x;
            }
            else
            {
                connected[x] = y;
                connected[y] = y;
                par[arr[x]] = y;
                par[arr[y]] = y;
            }
            cnt1[arr[x]]++;
            cnt1[arr[y]]++;
        }
        else if( connected[x] != 0 && connected[y] == 0 )
        {
            long parent = findparent(connected[x], connected);
            connected[y] = parent;
            cnt1[arr[y]]++;
            par[arr[y]] = parent;
        }
        else if( connected[x] == 0 && connected[y] != 0 )
        {
            long parent = findparent(connected[y], connected);
            connected[x] = parent;
            cnt1[arr[x]]++;
            par[arr[x]] = parent;
        }
        else
        {
            long parent = findparent(connected[y], connected);
            long parent1 = findparent(connected[x], connected);
            if( parent != parent1 && arr[x] == arr[y] && cnt[arr[x]] != -1 )
            {
                ans[arr[x]] = i;
            }
            step[parent1] = i;
            connected[parent1] = parent;
            par[arr[x]] = parent;
        }
        if( cnt1[arr[x]] == cnt[arr[x]] )
        {
            if( ans[arr[x]] == -1 )
            {
                ans[arr[x]] = i;
            }
        }
        if( cnt1[arr[x]] == cnt[arr[x]] && cnt[arr[x]] == 1 )
        {
            ans[arr[x]] = 0;
        }
        if( cnt1[arr[y]] == cnt[arr[y]] )
        {
            if( ans[arr[y]] == -1 )
            {
                ans[arr[y]] = i;
            }
        }
        if( cnt1[arr[y]] == cnt[arr[y]] && cnt[arr[y]] == 1 )
        {
            ans[arr[y]] = 0;
        }
    }
    for( i = 1 ; i <= N ; i++ )
    {
        int parent = findparent(i, connected);
        int parent1 = findparent(par[arr[i]], connected);
        if( par[arr[i]] != connected[i] )
        {
            if( parent1 == parent && step[par[arr[i]]] != 0 )
            {
                ans[arr[i]] = step[par[arr[i]]];
            }
            else if( parent1 == parent && step[connected[i]] != 0 )
            {
                ans[arr[i]] = step[connected[i]];
            }
            else if( parent1 != parent )
            {
                ans[arr[i]] = -1;
            }
        }
    }
    for( i = 1 ; i <= M ; i++ )
    {
        if( cnt[i] == 1 )
        {
            printf("%ldn", 0);
        }
        else
        {
            printf("%ldn", ans[i]);
        }
    }
    return 0;
}