HackerRank Jim and his LAN Party Problem Solution

HackerRank Jim and his LAN Party Solution

Yashwant Parihar,

In this post, we will solve HackerRank Jim and his LAN Party Problem Solution.

During the Steam Summer Sale, Jim’s N-1 friends have purchased M games, which are numbered from 1 to M. The games are multiplayer. Jim has invited his friends to his basement where they will play by making a LAN-Party.
Each friend has already decided the game he would like to play for the rest of the day. So there will be a group of friends who will play the same game together.
But then, they face a problem: Currently, none of the friends’ PCs are connected. So they have to be connected using the available Q wires. Jim decides to connect friends u, and vi with the ith wire one by one. So he starts with wire 1, then with wire 2 and so on.
A group can start playing their game, only if all the members are connected (if not directly, then there must exist a path connecting them). They want to start playing as soon as possible.
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.
Input Format
On the first line there will be N. M and Q each separated by a single space. On the second line we will give you N integers separated by a single space: The i-th integer denotes the game friend & wants to play (all between 1 and M). The next Q lines will denote Q wires: ith line denotes ith wire and is denoted by u, and v, pairs each separated by a single space.

Sample Input

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

Sample Output

3
4

Explanation

The group with the game 1 can play after the 3rd wire is added. The group with game 2 can play only after the 4th wire has been added because after adding the 4th wire, a path between (2,3) (3,4) and (2,4) gets created.

HackerRank Jim and his LAN Party Problem Solution

Jim and his LAN Party C Solution

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
  int end_val;
  struct _node *left;
  struct _node *right;
} node;
typedef struct _tree_node{
  enum {red,black} colour;
  int data;
  struct _tree_node *left,*right,*parent;
} tree_node;
void MM1(int x,int y);
void MM2(int x,int y);
void tra(tree_node *t2,tree_node **t1,int big);
int QQ(int x,int y);
void dfs(node *temp);
int search(tree_node *root,int data);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
int insert(tree_node **root,tree_node *x);
void delete(tree_node **root,tree_node *head,int data);
int p[100000],a[100000],ans[100000],sort_a[100000],q1[100000],q2[100000],game_left[100000],game_right[100000],group_left[100000],c=0,edge;
node *table[100000];
tree_node *tree_table[100000]={0},all_nodes1[100000],all_nodes2[100000];

int main(){
  int N,M,Q,i;
  node *temp;
  scanf("%d%d%d",&N,&M,&Q);
  for(i=0;i<N;i++)
    scanf("%d",a+i);
  for(i=0;i<Q;i++)
    scanf("%d%d",q1+i,q2+i);
  for(i=0;i<N;i++){
    p[i]=i;
    temp=(node*)malloc(sizeof(node));
    temp->end_val=i;
    temp->left=temp->right=NULL;
    table[i]=temp;
  }
  for(i=0;i<M;i++){
    game_left[i]=game_right[i]=-1;
    all_nodes1[i].data=i;
    all_nodes1[i].parent=all_nodes1[i].left=all_nodes1[i].right=NULL;
    all_nodes2[i].data=i;
    all_nodes2[i].parent=all_nodes2[i].left=all_nodes2[i].right=NULL;
  }
  for(i=0;i<Q;i++)
    if(!QQ(q1[i]-1,q2[i]-1))
      MM1(q1[i]-1,q2[i]-1);
  for(i=0;i<N;i++)
    if(p[i]==i){
      temp=table[i];
      dfs(temp);
    }
  for(i=0;i<N;i++){
    p[i]=i;
    group_left[sort_a[i]]=i;
  }
  for(i=0;i<N;i++){
    if(game_left[a[i]-1]==-1 || group_left[i]<game_left[a[i]-1])
      game_left[a[i]-1]=group_left[i];
    if(game_right[a[i]-1]==-1 || group_left[i]>game_right[a[i]-1])
      game_right[a[i]-1]=group_left[i];
  }
  for(i=0;i<M;i++)
    if(game_left[i]==game_right[i])
      ans[i]=0;
    else{
      ans[i]=-1;
      insert(tree_table+sort_a[game_left[i]],all_nodes1+i);
      insert(tree_table+sort_a[game_right[i]],all_nodes2+i);
    }
  for(i=0;i<N;i++)
    if(tree_table[i])
      sort_a[i]=1;
    else
      sort_a[i]=0;
  for(edge=0;edge<Q;edge++)
    if(!QQ(q1[edge]-1,q2[edge]-1))
      MM2(q1[edge]-1,q2[edge]-1);
  for(i=0;i<M;i++)
    printf("%d\n",ans[i]);
  return 0;
}
void MM1(int x,int y){
  int p1,p2;
  node *temp,*t1,*t2;
  p1=x;
  while(p[p1]!=p1)
    p1=p[p1];
  while(p[x]!=x){
    p2=p[x];
    p[x]=p1;
    x=p2;
  }
  t1=table[p1];
  p2=y;
  while(p[p2]!=p2)
    p2=p[p2];
  t2=table[p2];
  if(p2!=p1){
    p[p2]=p1;
    temp=(node*)malloc(sizeof(node));
    temp->left=t1;
    temp->right=t2;
    table[p1]=temp;
  }
  while(p[y]!=y){
    p2=p[y];
    p[y]=p1;
    y=p2;
  }
  return;
}
void MM2(int x,int y){
  int p1,p2,big;
  tree_node **t1,*t2;
  p1=x;
  while(p[p1]!=p1)
    p1=p[p1];
  while(p[x]!=x){
    p2=p[x];
    p[x]=p1;
    x=p2;
  }
  p2=y;
  while(p[p2]!=p2)
    p2=p[p2];
  if(p2!=p1){
    p[p2]=p1;
    t1=(sort_a[p1]>sort_a[p2])?&tree_table[p1]:&tree_table[p2];
    t2=(sort_a[p1]>sort_a[p2])?tree_table[p2]:tree_table[p1];
    big=(sort_a[p1]>sort_a[p2])?p1:p2;
    tra(t2,t1,big);
    if(big!=p1){
      tree_table[p1]=tree_table[p2];
      sort_a[p1]=sort_a[p2];
    }
  }
  while(p[y]!=y){
    p2=p[y];
    p[y]=p1;
    y=p2;
  }
  return;
}
void tra(tree_node *t2,tree_node **t1,int big){
  if(!t2)
    return;
  tra(t2->left,t1,big);
  tra(t2->right,t1,big);
  t2->parent=t2->left=t2->right=NULL;
  if(insert(t1,t2))
    sort_a[big]++;
  else{
    ans[t2->data]=edge+1;
    delete(t1,*t1,t2->data);
    sort_a[big]--;
  }
  return;
}
int QQ(int x,int y){
  int p1,p2,ans;
  p1=x;
  while(p[p1]!=p1)
    p1=p[p1];
  ans=p1;
  while(p[x]!=x){
    p2=p[x];
    p[x]=p1;
    x=p2;
  }
  p1=y;
  while(p[p1]!=p1)
    p1=p[p1];
  ans=(ans==p1);
  while(p[y]!=y){
    p2=p[y];
    p[y]=p1;
    y=p2;
  }
  return ans;
}
void dfs(node *temp){
  if(!temp)
    return;
  if(temp->left==NULL && temp->right==NULL){
    sort_a[c++]=temp->end_val;
    return;
  }
  dfs(temp->left);
  dfs(temp->right);
  return;
}
int search(tree_node *root,int data){
  if(!root)
    return 0;
  if(root->data==data)
    return 1;
  if(data<root->data)
    return search(root->left,data);
  return search(root->right,data);
}
void left_rotate(tree_node **root,tree_node *x){
  tree_node *y;
  y=x->right;
  if(!y) return;
  x->right=y->left;
  if(y->left)
    y->left->parent=x;
  y->parent=x->parent;
  if(x->parent==NULL) *root=y;
  else
    if(x==x->parent->left)
      x->parent->left=y;
    else
      x->parent->right=y;
  y->left=x;
  x->parent=y;
  return;
}
void right_rotate(tree_node **root,tree_node *y){
  tree_node *x;
  x=y->left;
  if(!x) return;
  y->left=x->right;
  if(x->right)
    x->right->parent=y;
  x->parent=y->parent;
  if(y->parent==NULL) *root=x;
  else
    if(y==y->parent->right)
      y->parent->right=x;
    else
      y->parent->left=x;
  x->right=y;
  y->parent=x;
  return;
}
void reconstruct(tree_node **root,tree_node *x){
  tree_node *y,*z;
  y=x->parent;
  z=x->parent->parent;
  x->colour=black;
  z->colour=red;
  x->parent=z->parent;
  if(z->parent==NULL)
    *root=x;
  else if(z==z->parent->left)
    z->parent->left=x;
  else
    z->parent->right=x;
  if(z->left==y){
    x->left=y;
    x->right=z;
  }
  else{
    x->left=z;
    x->right=y;
  }
  y->parent=z->parent=x;
  y->left=y->right=z->left=z->right=NULL;
  return;
}
int normal_insert(tree_node **root,tree_node *x){
  if(*root==NULL)
    *root=x;
  else if((*root)->data==x->data)
    return 0;
  else{
    x->parent=*root;
    if((*root)->data>x->data)
      return normal_insert(&((*root)->left),x);
    else
      return normal_insert(&((*root)->right),x);
  }
  return 1;
}
int insert(tree_node **root,tree_node *x){
  if(!normal_insert(root,x))
    return 0;
  tree_node *y;
  x->colour=red;
  while(x!=*root && x->parent->colour==red){
    if(x->parent==x->parent->parent->left){
      y=x->parent->parent->right;
      if(!y)
        if(x==x->parent->left){
          x->parent->colour=black;
          x->parent->parent->colour=red;
          right_rotate(root,x->parent->parent);
        }
        else{
          y=x->parent;
          reconstruct(root,x);
          x=y;
        }
      else if(y->colour==red){
        x->parent->colour=black;
        y->colour=black;
        x->parent->parent->colour=red;
        x=x->parent->parent;
      }
      else{
        if(x==x->parent->right){
          x=x->parent;
          left_rotate(root,x);
        }
        x->parent->colour=black;
        x->parent->parent->colour=red;
        right_rotate(root,x->parent->parent);
      }
    }
    else{
      y=x->parent->parent->left;
      if(!y)
        if(x==x->parent->right){
          x->parent->colour=black;
          x->parent->parent->colour=red;
          left_rotate(root,x->parent->parent);
        }
        else{
          y=x->parent;
          reconstruct(root,x);
          x=y;
        }
      else if(y->colour==red){
        x->parent->colour=black;
        y->colour=black;
        x->parent->parent->colour=red;
        x=x->parent->parent;
      }
      else{
        if(x==x->parent->left){
          x=x->parent;
          right_rotate(root,x);
        }
        x->parent->colour=black;
        x->parent->parent->colour=red;
        left_rotate(root,x->parent->parent);
      }
    }
  }
  (*root)->colour=black;
  return 1;
}
void delete(tree_node **root,tree_node *head,int data){
  tree_node *db,*parent,*brother,*child,none;
  if(!head)
    return;
  if(data<head->data){
    delete(root,head->left,data);
    return;
  }
  if(data>head->data){
    delete(root,head->right,data);
    return;
  }
  if(data==head->data){
    if(head->left && head->right){
      db=head->right;
      while(db->left)
        db=db->left;
      head->data=db->data;
      head=db;
    }
    if(head->left==NULL && head->right==NULL){
      parent=head->parent;
      if(!parent){
        *root=NULL;
        return;
      }
      brother=(parent->left==head)?parent->right:parent->left;
      if(head->colour==red){
        if(parent->left==head)
          parent->left=NULL;
        else
          parent->right=NULL;
        return;
      }
      if(parent->left==head)
        parent->left=&none;
      else
        parent->right=&none;
      none.parent=parent;
      none.colour=black;
      db=&none;
    }
    else{
      parent=head->parent;
      child=(!head->left)?head->right:head->left;
      if(!parent){
        *root=child;
        child->parent=NULL;
        child->colour=black;
        return;
      }
      if(parent->left==head)
        parent->left=child;
      else
        parent->right=child;
      child->parent=parent;
      db=child;
    }
  }
  while(db){
    if(db->colour==red){
      db->colour=black;
      return;
    }
    if(db==*root)
      return;
    parent=db->parent;
    brother=(parent->left==db)?parent->right:parent->left;
    if(!brother)
      db=parent;
    else if(brother==parent->right){
      if(brother->colour==black && brother->right && brother->right->colour==red){
        brother->colour=parent->colour;
        brother->right->colour=black;
        parent->colour=black;
        left_rotate(root,parent);
        if(db==&none)
          parent->left=NULL;
        return;
      }
      else if(brother->colour==black && brother->left && brother->left->colour==red){
        brother->left->colour=parent->colour;
        parent->colour=black;
        right_rotate(root,brother);
        left_rotate(root,parent);
        if(db==&none)
          parent->left=NULL;
        return;
      }
      else if(brother->colour==black){
        brother->colour=red;
        if(db==&none)
          parent->left=NULL;
        db=parent;
      }
      else{
        brother->colour=black;
        parent->colour=red;
        left_rotate(root,parent);
      }
    }
    else{
      if(brother->colour==black && brother->left && brother->left->colour==red){
        brother->colour=parent->colour;
        brother->left->colour=black;
        parent->colour=black;
        right_rotate(root,parent);
        if(db==&none)
          parent->right=NULL;
        return;
      }
      else if(brother->colour==black && brother->right && brother->right->colour==red){
        brother->right->colour=parent->colour;
        parent->colour=black;
        left_rotate(root,brother);
        right_rotate(root,parent);
        if(db==&none)
          parent->right=NULL;
        return;
      }
      else if(brother->colour==black){
        brother->colour=red;
        if(db==&none)
          parent->right=NULL;
        db=parent;
      }
      else{
        brother->colour=black;
        parent->colour=red;
        right_rotate(root,parent);
      }
    }
  }
  return;
}

Jim and his LAN Party C++ Solution

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);
    
namespace waldek
{
    template<class T=size_t>
    class DisjointSet
    {
    public:
        typedef T type;
        ///@returns number of independent sets/*
    
        type size()const { return m_size; }
        ///@returns size of set contains 'x'
        type size(type x) { return m_arr[find(x)].size;  }
        ///@returns size of bigest set
        type getMax()const{ return m_max; }
        
        ///@returns set where x belong to
        size_t find(type x)
        {
            auto res = m_arr.find(x);
            if(res==m_arr.end())
            {
                m_arr[x] = {x,1};
                m_size++;
                m_max = std::max(m_max, type(1) );
            }
            auto root = x;
            
            while( m_arr[root].parent != root )
                root = m_arr[root].parent;
            
            while( m_arr[x].parent != root )
            {
                auto parent = m_arr[x].parent;
                m_arr[x].parent = root;
                x = parent;
            }
            
            return root;
        }
        
        ///@returns merged set
        type merge(type a, type b)
        {
            type aa = find(a);
            type bb = find(b);
            
            if(aa==bb)
                return aa;
            else if(aa<bb)
            {
                m_arr[bb].parent = aa;
                m_arr[aa].size += m_arr[bb].size;
                m_size--;
                m_max = std::max(m_max, m_arr[aa].size);
                return aa;
            }
            else
            {
                m_arr[aa].parent = bb;
                m_arr[bb].size += m_arr[aa].size;
                m_size--;
                m_max = std::max(m_max, m_arr[bb].size);
                return bb;
            }
        }
        
    private:
        struct Set
        {
            type parent;
            type size;
        };
        
        std::unordered_map<type,Set> m_arr;
        type           m_size=0;
        type           m_max=0;
        
    };

}

int checkNetwork(waldek::DisjointSet<>& ds, vector<int>& checkpoints, int start)
{
    cout<<"  check:"<<checkpoints[start];
    for(int i=start; i<(int)checkpoints.size(); i++)
    {
        cout<<","<<checkpoints[i];
        if( ds.find(checkpoints[0])!=ds.find(checkpoints[i]) )
        {   cout<<" -> "<<checkpoints[i]<<":"<<i<<endl;
            return i;
        }
    }
    cout<<" -> -1"<<endl;
    return -1;
}

vector<int> lanParty(//-------------------------------------------------------------
        const vector<int>& games, 
        const vector<vector<int>>& wires, 
        int m
    )
{
    vector<int> ret(m,0);
    vector<vector<int>> g2f(m+1);
    for(int i=0; i<(int)games.size() ; i++)
        g2f[games[i]].push_back(i+1);

    waldek::DisjointSet<> network;

    int cable =0;
    int res =0;

    for(int game=1 ; game<=m ; ++game)
    {
        if(g2f[game].size()==1)
        {
            ret[game-1]=0;
            continue;
        }
        if(wires.size()==0 && g2f[game].size()>1)
        {    
            ret[game-1]=-1;
            continue;
        }

        res =0;

        cout<<"game:"<<game<<endl;
        while(cable<(int)wires.size() && res!=-1)
        {
            ret[game-1]=cable+1;
            cout<<"  add: "<<cable+1
                <<"   "<<wires[cable][0]
                <<","<<wires[cable][1]
                <<"  ,res:"<<ret[game-1]<<endl;
            network.merge(wires[cable][0], wires[cable][1]);
            res= checkNetwork(network, g2f[game], res);
            cable++;
        }
        if(cable>=(int)wires.size() && res>0) ret[game-1]=-1;
        else if(
            cable>=(int)wires.size() && 
            game>1 && 
            (ret[game-1]<ret[game-2] || ret[game-2]==-1)
        ){
            int r =checkNetwork(network,g2f[game],0);
            ret[game-1]= r!=-1 ? -1 : cable;
            
        } 
        
    }

    return ret;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nmq_temp;
    getline(cin, nmq_temp);

    vector<string> nmq = split_string(nmq_temp);

    int n = stoi(nmq[0]);

    int m = stoi(nmq[1]);

    int q = stoi(nmq[2]);

    string games_temp_temp;
    getline(cin, games_temp_temp);

    vector<string> games_temp = split_string(games_temp_temp);

    vector<int> games(n);

    for (int games_itr = 0; games_itr < n; games_itr++) {
        int games_item = stoi(games_temp[games_itr]);

        games[games_itr] = games_item;
    }

    vector<vector<int>> wires(q);
    for (int wires_row_itr = 0; wires_row_itr < q; wires_row_itr++) {
        wires[wires_row_itr].resize(2);

        for (int wires_column_itr = 0; wires_column_itr < 2; wires_column_itr++) {
            cin >> wires[wires_row_itr][wires_column_itr];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    vector<int> result = lanParty(games, wires, m);

    for (int result_itr = 0; result_itr < (int)result.size(); result_itr++) {
        fout << result[result_itr];

        if (result_itr != (int)result.size() - 1) {
            fout << "\n";
        }
    }

    fout << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Jim and his LAN Party C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    public class PC {
        public int MyGoal;
        
        public int MyNetwork;
        public PC(int myG) {
            MyGoal = myG;
            MyNetwork = 0;
        }
    }
    public class Network {
        public int ID;
        public Network MyNetwork;
//        public Dictionary<int, int> Counts;
        public Dictionary<int, HashSet<int>> Counts;
        public Network(int nid) {
            ID = nid;
            Counts = new Dictionary<int, HashSet<int>>();
        }        
    }
    /*
     * Complete the lanParty function below.
     */
    static Network[] networks;
    static int[] netParents;
    static int[] lanParty(int[] games, int[][] wires, int M) {
        int N = games.Length;
        int Q = wires.Length;
        PC[] pcs = new PC[N];
        networks = new Network[N];
        netParents = new int[N];
        int[] goal = new int[M];
        int[] fin = new int[M];
        int nextNetwork = 1;
        for(int i=0; i<N; i++) {
            pcs[i] = new PC(games[i]-1);
            goal[games[i]-1]++;
        }
        for(int i=0; i<fin.Length; i++) {
            if(goal[i] != 1) {
                fin[i] = -1;
            }
        }
        for(int i=0; i<Q; i++) {
            int a = wires[i][0]-1;
            int b = wires[i][1]-1;
            PC A = pcs[a];
            PC B = pcs[b];
            if(A.MyNetwork == 0 && B.MyNetwork == 0) {
                Network temp = new Network(nextNetwork);
                nextNetwork++;
                networks[temp.ID] = temp;
                A.MyNetwork = temp.ID;
                B.MyNetwork = temp.ID;
                if(A.MyGoal == B.MyGoal) {
                    HashSet<int> hs = new HashSet<int>();
                    hs.Add(a);
                    hs.Add(b);
                    temp.Counts.Add(A.MyGoal, hs);
                    if(fin[A.MyGoal] == -1 && goal[A.MyGoal] == 2) {
                        fin[A.MyGoal] = i+1;
                    }
                } else {
                    HashSet<int> hsA = new HashSet<int>();
                    HashSet<int> hsB = new HashSet<int>();
                    hsA.Add(a);
                    hsB.Add(b);
                    temp.Counts.Add(A.MyGoal, hsA);
                    temp.Counts.Add(B.MyGoal, hsB);
                }
            } else if(A.MyNetwork == 0) {
                Network temp = GetNetwork(B.MyNetwork);
                B.MyNetwork = temp.ID;
                A.MyNetwork = temp.ID;
                if(goal[A.MyGoal] != 1) {
                    if(!temp.Counts.ContainsKey(A.MyGoal)) {
                        temp.Counts.Add(A.MyGoal, new HashSet<int>());
                        temp.Counts[A.MyGoal].Add(a);
                    } else if(!temp.Counts[A.MyGoal].Contains(a)) {
                        temp.Counts[A.MyGoal].Add(a);
                    }
                    if(fin[A.MyGoal] == -1 && temp.Counts[A.MyGoal].Count >= goal[A.MyGoal]) {
                        fin[A.MyGoal] = i+1;
                    }
                }
            } else if(B.MyNetwork == 0){ 
                Network temp = GetNetwork(A.MyNetwork);
                A.MyNetwork = temp.ID;
                B.MyNetwork = temp.ID;
                if(goal[B.MyGoal] != 1) {
                    if(!temp.Counts.ContainsKey(B.MyGoal)) {
                        temp.Counts.Add(B.MyGoal, new HashSet<int>());
                        temp.Counts[B.MyGoal].Add(b);
                    } else if(!temp.Counts[B.MyGoal].Contains(b)) {
                        temp.Counts[B.MyGoal].Add(b);
                    }
                    if(fin[B.MyGoal] == -1 && temp.Counts[B.MyGoal].Count >= goal[B.MyGoal]) {
                        fin[B.MyGoal] = i+1;
                    }
                }
            } else {
                Network to = GetNetwork(A.MyNetwork);
                Network fro = GetNetwork(B.MyNetwork);
                foreach(KeyValuePair<int, HashSet<int>> v in fro.Counts) {
                    HashSet<int> temp;
                    if(!to.Counts.ContainsKey(v.Key)) {
                        temp = new HashSet<int>();
                        to.Counts.Add(v.Key, temp);
                    } else {
                        temp = to.Counts[v.Key];
                    }
                    foreach(var v2 in v.Value) {
                        if(!temp.Contains(v2)) {
                            temp.Add(v2);
                        }
                    }
                    if(fin[v.Key] == -1 && temp.Count >= goal[v.Key]) {
                        fin[v.Key] = i+1;
                    }
                }
                A.MyNetwork = to.ID;
                B.MyNetwork = to.ID;
            }
        }
        return fin;
    }
    
    public static Network GetNetwork(int i) {
        while(netParents[i] != 0) {
            i = netParents[i];
        }
        if(networks[i] == null) { Console.WriteLine("NULL NETWORK"); }
        return networks[i];
    }

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

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

        int n = Convert.ToInt32(nmq[0]);

        int m = Convert.ToInt32(nmq[1]);

        int q = Convert.ToInt32(nmq[2]);

        int[] games = Array.ConvertAll(Console.ReadLine().Split(' '), gamesTemp => Convert.ToInt32(gamesTemp))
        ;

        int[][] wires = new int[q][];

        for (int wiresRowItr = 0; wiresRowItr < q; wiresRowItr++) {
            wires[wiresRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), wiresTemp => Convert.ToInt32(wiresTemp));
        }

        int[] result = lanParty(games, wires, m);

        textWriter.WriteLine(string.Join("\n", result));

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

Jim and his LAN Party Java Solution

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

Jim and his LAN Party JavaScript Solution

function processData(input) {
    //Enter your code here
    class LanParty {
        constructor(input) {
            this.gameCount = 0;
            this.successWires = [];
            this.changedMergeGameIds = [];
            this.changedMergeIdCount = 0;
            this._input = input;
            this._currentWire = 0;
            this.nets = [0]; // net ID or net for each player
            this.playerPerGameCounts = [0];
        }

        _parseInput() {
            const lines = this._input.split('\n');

            const constants = this._parseNumbers(lines[0]);
            this.playerCount = constants[0];
            this.gameCount = constants[1];
            this.wireCount = constants[2];

            this.playerGames = this._parseNumbers(lines[1], 1);

            this.wires = [];
            for (let i = 0; i < this.wireCount; i++) {
                this.wires.push(this._parseNumbers(lines[2 + i]));
            }
        }

        _parseNumbers(line, startIndex = 0) {
            const array = line.split(' ').map(x => parseInt(x));
            return startIndex === 1 ? [0].concat(array) : array;
        }

        _prepareDataStructure() {
            for (let p = 1; p <= this.playerCount; p++) {
                this.nets[p] = p;
            }

            // NB: for n players, n-1 connections needed
            for (let p = 1; p <= this.playerCount; p++) {
                const gameId = this.playerGames[p];
                const count = this.playerPerGameCounts[gameId];
                if (count === undefined) {
                    this.playerPerGameCounts[gameId] = 0;
                } else {
                    this.playerPerGameCounts[gameId] = count + 1;
                }
            }

            this.successWires = new Array(this.gameCount + 1);
            this.successWires[0] = -99; // first value never used
            for (let g = 1; g <= this.gameCount; g++) {
                // if more than 1 player in game, we need to connect (-1 if failed)
                // otherwise we are ready to play from wire #0 (e.g. Test #3)
                this.successWires[g] = this.playerPerGameCounts[g] >= 1 ? -1 : 0;
            }
        }

        solveProblem() {
            this._parseInput();
            this._prepareDataStructure();

            // Connect players with wires
            for (let w = 0; w < this.wireCount; w++) {
                const wire = this.wires[w];
                const a = wire[0], b = wire[1];
                this._connect(a, b, w + 1);
            }
            return this.successWires.slice(1);
        }

        _connect(p1, p2, wireIndex) {
            this._currentWire = wireIndex;
            const n1 = this.nets[p1];
            const n2 = this.nets[p2];
            if (n1 === n2) return; // already connected

            const id1 = n1.id || n1;
            const id2 = n2.id || n2;

            // Merge groups, keep lowest ID for group ID of the whole

            if (n2 === id2) { // n2 is an ID
                if (n1 === id1) { // both an ID
                    new Net(this, id1).add(id2);
                } else { // n1 is a net
                    n1.add(id2);
                }
            } else { // n2 is a net
                if (n1 === id1) { // n1 is an ID
                    n2.add(id1);
                } else { // both are nets
                    n1.merge(n2);
                }
            }
        }

        countConnectedPlayer(gameId) {
            if (--this.playerPerGameCounts[gameId] === 0) {
                this.successWires[gameId] = this._currentWire;
            }
        }
    }

    class Net {
        constructor(solver, id) {
            this.solver = solver;
            this.id = id;
            this.players = [id];
            this.countMap = {}; // gameId => count

            const gameId = this.solver.playerGames[id];
            this.countMap[gameId] = 1;
            this.solver.nets[id] = this;
        }

        add(id) {
            this.players.push(id);
            const gameId = this.solver.playerGames[id];
            this._countGame(gameId);
            this.solver.nets[id] = this;
        }

        _countGame(gameId) {
            if (this.countMap[gameId]) {
                this.solver.countConnectedPlayer(gameId);
            } else {
                this.countMap[gameId] = 1;
            }
        }

        merge(n2) {
            for (let gameId in n2.countMap) {
                this._countGame(gameId);
            }
            const nets = this.solver.nets;
            for (let i = 0; i < n2.players.length; i++) {
                const id = n2.players[i];
                this.players.push(id);
                nets[id] = this;
            }
        }
    }

//---

    const result = new LanParty(input).solveProblem();
    for (let i = 0; i < result.length; i++) {
        console.log(result[i]);
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Jim and his LAN Party Python Solution

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)
c C# C++ HackerRank Solutions java javascript python