We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Jim and his LAN Party
  5. Discussions

Jim and his LAN Party

Sort by

recency

|

17 Discussions

|

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Jim and his LAN Party Solution

  • mineman1012221
     + 0 comments

    Here is the solution of Jim and his LAN Party Click here

  • thecodingsoluti2
     + 0 comments

    Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-jim-and-his-FAN-problem-solution.html

  • zambogo7
     + 1 comment

    def find_wire(m, q, games, wires): # Create a union-find set uf = UnionFind(m)

    # Iterate through the wires
for wire in wires:
    # Connect the two friends and merge their groups
    uf.union(wire[0]-1, wire[1]-1)

    # Check if the group that the friends belong to now contains all the friends
    # in the same game
    game = games[wire[0]-1]
    if uf.find(game-1) == uf.find(game):
        print(wire[0])
        return

# If no group contains all the friends in the same game, print -1
print(-1)

    Union-find set class

    class UnionFind: def init(self, n): self.parent = [i for i in range(n)] self.size = [1] * n

    def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

def union(self, x, y):
    x_root = self.find(x)
    y_root = self.find(y)
    if x_root == y_root:
        return
    if self.size[x_root] < self.size[y_root]:
        self.parent[x_root] = y_root
        self.size[y_root] += self.size[x_root]
    else:
        self.parent[y_root] = x_root
        self.size[x_root] += self.size[y_root]

    Read input

    m, n, q = map(int, input().split()) games = list(map(int, input().split())) wires = [tuple(map(int, input().split())) for _ in range(q)]

    Find the wire

    find_wire(m, q, games, wires)

  • TChalla
     + 1 comment

    Python3 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)