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