Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

部活動調査

A 高校の生徒会長である明は、A 高校の生徒がどの部活動に所属しているかを調査することにした。A高校には 1 から N の番号が付けられた N 人の生徒と、1 から M の番号が付けられた M 種類の部活動がある。各部活動に人数制限はなく、0 人の部活動もありえる。ただし、A 高校の校則では生徒はひとつの部活動までしか所属できない。生徒は全員この校則を守っている。

明は生徒会員に調査を依頼し、各行が次のいずれかであるような K 行の記録を入手した。

 生徒 a と生徒 b は同じ部活動に所属している。

 生徒 c は部活動 x に所属している。

しかし、この記録には誰かが校則違反になってしまうような矛盾があるかもしれない。明は１行目から順に見ていき、矛盾があると判断できる最初の行を探すことにした。

K 行の記録が与えられたとき、矛盾があると判断できる最初の行の番号を求めるプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N M K
record1
record2
:
recordK

１行目に生徒の人数 N (1 ≤ N ≤ 100000)、部活動の種類の数 M (1 ≤ M ≤ 100000)、記録の行数 K (1 ≤ K ≤ 200000) が与えられる。続く K 行に記録の各行 recordi が、以下のいずれかの形式で与えられる。

1 a b

または

2 c x

先頭の数字が「1」のとき、生徒 a (1 ≤ a ≤ N) と生徒 b (1 ≤ b ≤ N) が同じ部活動に所属していることを示す。ただし、a &ne; b である。

先頭の数字が「2」のとき、生徒 c (1 ≤ c ≤ N) が部活動 x (1 ≤ x ≤ M) に所属していることを示す。

Output

矛盾があると判断できる最初の行の番号を１行に出力する。見つからない場合は 0 を１行に出力する。

Sample Input 1

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

Sample Output 1

4

Sample Input 2

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

Sample Output 2

0

Sample Input 3

3 2 2
1 1 2
2 1 1

Sample Output 3

0



Sample input:
3 2 5
1 1 2
1 2 3
2 1 1
2 3 2
2 2 1


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


class ClubConflictException(Exception):
    pass


class Student:
    def __init__(self, number):
        self.name = number
        self.club = -1
        self.in_same_club = []

    def set_club(self, clb, order_from=None):
        if not self.is_belong():
            self.club = clb
            if not order_from is None:
                try:
                    self.in_same_club.remove(order_from)
                except ValueError:
                    pass
            self.synchronize_club()
        elif self.club == clb:
            if not order_from is None:
                try:
                    self.in_same_club.remove(order_from)
                except ValueError:
                    pass
        else:
            raise ClubConflictException

    def is_belong(self):
        if self.club == -1:
            return False
        return True

    def synchronize_club(self):
        if not self.in_same_club:
            pass
        else:
            to_synchro = self.in_same_club[:]
            for std in to_synchro:
                std.set_club(self.club, self)
                self.in_same_club.remove(std)

class Club:
    def __init__(self, number):
        self.name = number


class Commission:
    def __init__(self):
        self.student_list = []
        self.club_list = []

    def set_same_club(self, std1, std2):
        student1 = self.check_std(std1)
        student2 = self.check_std(std2)

        if student1.is_belong():
            student2.set_club(student1.club)
        elif student2.is_belong():
            student1.set_club(student2.club)
        else:
            student1.in_same_club.append(student2)
            student2.in_same_club.append(student1)

    def link_std_and_club(self, std, club):
        student = self.check_std(std)
        clb = self.check_club(club)

        student.set_club(clb)

    def check_std(self, std):
        if self.is_made_std(std):
            return self.search_list(std, self.student_list)
        return self.make_std(std)

    def check_club(self, club):
        if self.is_made_club(club):
            return self.search_list(club, self.club_list)
        return self.make_club(club)

    def search_list(self, element, org_list):
        list_to_dict = {elm.name: elm for elm in org_list}
        return list_to_dict[element]

    def is_made_std(self, std):
        std_n_list = [student.name for student in self.student_list]
        if std in std_n_list:
            return True
        return False

    def make_std(self, std):
        student = Student(std)
        self.student_list.append(student)
        return student

    def is_made_club(self, clb):
        club_n_list = [club.name for club in self.club_list]
        if clb in club_n_list:
            return True
        return False

    def make_club(self, club):
        clb = Club(club)
        self.club_list.append(clb)
        return clb


if __name__ == '__main__':
    N, M, K = map(int, input().split())
    akira = Commission()
    for i in range(1, K+1):
        rtype, x1, x2 = map(int, input().split())

        if rtype == 1:
            try:
                akira.set_same_club(x1, x2)
            except ClubConflictException:
                print(i)
                break

        elif rtype == 2:
            try:
                akira.link_std_and_club(x1, x2)
            except ClubConflictException:
                print(i)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
*parent, = range(n+m)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
for i in range(k):
    a, b, c = map(int, input().split())
    b -= 1; c -= 1
    if a == 1:
        pb = root(m+b); pc = root(m+c)
        if pb < m and pc < m and pb != pc:
            print(i+1)
            break
        unite(pb, pc)
    else:
        pb = root(m+b)
        if pb < m and pb != c:
            print(i+1)
            break
        unite(c, pb)
else:
    print(0)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
parent = [i for i in range(n)]
club = [-1 for _ in range(n)]

def find(x):
  if x == parent[x]:
    return x
  ret =  find(parent[x])
  parent[x] = ret
  return ret

for count in range(1, k + 1):
  t, a, b = map(int, input().split())
  a -= 1
  b -= 1
  if t == 1:
    p_a = find(a)
    p_b = find(b)
    c_a = club[p_a]
    c_b = club[p_b]
    if c_a >= 0 and c_b >= 0 and c_a != c_b:
      print(count)
      break
    if c_a < 0 and c_b >= 0:
      club[p_a] = c_b
    parent[p_b] = p_a

  else:
    p_a = find(a)
    if club[p_a] < 0:
      club[p_a] = b
    if club[p_a] >= 0 and club[p_a] != b:
      print(count)
      break
else:
  print(0)