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.

HackerRank Jim and his LAN Party problem solution


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)
    

{"mode":"full","isActive":false}


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();
  }
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}


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("%ld\n", 0);
        }
        else
        {
            printf("%ld\n", ans[i]);
        }
    }
    return 0;
}

{"mode":"full","isActive":false}