Problem:


魔法陣

人里離れた森の奥深くに、マリーという名の魔女が住んでいました。彼女は魔女なので、食料・水・燃料など、生活に必要なものを魔法によってまかなっています。

彼女の魔法は、魔力を込めたいくつかの石と紐を使って、魔法陣を描くことによって発動します。この魔法陣は、石を設置し、いくつかの石のペアを紐で繋ぐことで描かれます。ただし、紐は弛んでいてはいけません。さらに、どの紐も、(両端を除いて) 他の紐や石に触れてはいけません。もちろん、同じ場所に複数の石を置くこともできません。この制約が守られる限り、石と石の位置関係や紐の長さに制限はありません。また、石は十分小さいので点として扱うことができ、紐は十分細いので線分として扱うことができます。さらに、彼女は同じ石のペアを2本以上の紐で繋ぐことも、ある紐の両端を同じ石に結ぶこともありません。

マリーは初め、石を彼女の家の平らな壁に貼り付けて魔法陣を描いていました。しかし、彼女はやがて、どうしても作ることのできない魔法陣があることに気付いたのです。しばらくして、彼女は魔法陣を平らな壁、つまり二次元平面の上で作ることができるか判定する方法を編み出しました。ある魔法陣は、次のような部分を含む場合、またその場合に限って、二次元平面上で作ることができないのです。

        

図１ 頂点数 5 の完全グラフ

図２ 頂点数 3, 3 の完全二部グラフ

このような魔法陣を描くために、彼女は石を空中に固定する魔法を編み出しました。三次元空間では、これらの魔法陣も描くことができるのです。それどころか、どんな魔法陣も三次元空間中では描くことができることを彼女は突き止めたのです。

さて、ここからが問題です。ある日マリーは、彼女の家の玄関に足元灯の魔法陣を作ることにしました。しかし、彼女は既に狭い玄関にいろいろな魔法陣を設置していたので、足元灯の魔法陣を、残された唯一のスペースである一次元の直線の上に描かなければなりません。彼女が設計したいくつかの足元灯の魔法陣について、それが直線の上に描けるかどうかを判定し、描ける場合 yes と、そうでない場合 no と出力するプログラムを作成して下さい。

魔法陣は、石の個数 n、紐の本数 m、m 個の紐の情報で与えられます。紐は、その両端の石の番号 u、v で表されます。石には 1 から n までの番号が与えられ、n は 1 以上 100,000 以下、m は 0 以上 1,000,000 以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。

1 行目 石の個数 n 紐の本数 m（整数 整数；半角空白区切り）

2 行目 第1の紐の情報 u v（整数 整数；半角空白区切り）

3 行目 第2の紐の情報

:

m+1 行目 第 m の紐の情報

データセットの数は 20 を超えません。

出力

入力データセットごとに、yes または no と１行に出力します。

入力例

5 4
1 2
2 3
3 4
4 5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 0
0 0

出力例

yes
no
yes



Sample input:
5 4
1 2
2 3
3 4
4 5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 0
0 0


Sample output:
yes
no
yes

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  #par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = Counter()
    flag = False
    if m == 0:
      print("yes")
      continue
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if counter.most_common()[0][1] > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()

Submission status: Accepted

Solution code:
while(1):
    [n,m]=map(int,raw_input().split())
    if n==0:    break
    D=[[] for i in range(n+1)]
    D[0]=range(1,n+1)
    nflg=0
    for i in range(m):
        [u,v]=map(int,raw_input().split())
        D[u].append(v)
        D[v].append(u)
        if len(D[u])>2 or len(D[v])>2:
            nflg=1
    if nflg:
        print 'no'
    else:
        bkf=0
        while (len(D[0])>0):
            st=D[0].pop()
            if len(D[st])==2:
                D[0].append(st)
            st0=st
            while len(D[st])!=0:
               nxt=D[st].pop()
               if nxt!=st0:
                   D[0].remove(nxt)
                   D[nxt].remove(st)
                   st=nxt
               else:
                   print 'no'
                   bkf=1
                   break
            if bkf:    break
        else:
            print 'yes'

Submission status: Accepted

Solution code:
# AOJ 0251: Magic Square
# Python3 2018.6.25 bal4u

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

while True:
	n, m = map(int, input().split())
	if n == 0: break
	n += 1
	u = UnionSet(n)
	f = [0]*n
	ans = True
	for i in range(m):
		if ans:
			a, b = map(int, input().split())
			f[a] += 1
			f[b] += 1
			if f[a] > 2: ans = False
			if f[b] > 2: ans = False
			if u.connected(a, b): ans = False
			u.unite(a, b)
		else: input()
	print("yes" if ans else "no")

Submission status: Accepted

Solution code:
from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = Counter()
    flag = False
    if m == 0:
      print("yes")
      continue
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if counter.most_common()[0][1] > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()

Submission status: Accepted

Solution code:
from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = [0] * n
    flag = False
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if max(counter) > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()

Submission status: Runtime Error

Solution code:
while(1):
    [n,m]=map(int,raw_input().split())
    if n==0:    break
    D=[[] for i in range(n+1)]
    D[0]=range(1,n+1)
    nflg=0
    for i in range(m):
        [u,v]=map(int,raw_input().split())
        D[u].append(v)
        D[v].append(u)
        if len(D[u])>2 or len(D[v])>2:
            nflg=1
    if nflg:
        print 'no'
    else:
        bkf=0
        while (len(D[0])>0):
            st=D[0].pop()
            st0=st
            while len(D[st])!=0:
               nxt=D[st].pop()
               if nxt!=st0:
                   D[0].remove(nxt)
                   D[nxt].remove(st)
                   st=nxt
               else:
                   print 'no'
                   bkf=1
                   break
            if bkf:    break
        else:
            print 'yes'