【AtCoder 初心者】ACL Beginner の参加記録 ~感想と解法~【python】

ABC179に引き続き，連続での参加となります．

A問題：A – Repeat ACL

何も不安がることはない．

K=int(input())

print("ACL"*K)

B問題：Integer Preference

a~bとc~dの区間に注目する．

数字が被っていない場合(以下の2パターン)はNo，それ以外はYesという風に考える．

ソースコードは以下の通り．

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
  
a,b,c,d=input2()

if d<a or b<c:
	print("No")
else:
	print("Yes")

C問題：Connect Cities

鬼門のC問題．

N個の都市間を全て行き来できる(到達可能)ように道路をつなぎ，その数を答えよという問題．

まず以下の入力を考える．

5 2
1 4
2 3

このケースでは「都市1-都市4」と「都市2-都市3」が道路で繋がっており，「都市5」は独立している状態．この状態から全ての都市を行き来するためには，以下のように道路をつなげば良い．

上図のように，「都市1-都市2」と「都市2-都市5」間を道路でつなぐと，全ての都市に行き来できるようになる．

このように，図で書くと分かるのだが，「部分グラフの数-1」がこの問題の解となる．

そこで部分グラフの数を求めるのに使うのが「Union-Find」というアルゴリズムである．

この問題をみた途端，「Union-Findで一発じゃね？」って考えられたら，あなたの勝ちです．

ソースコードは以下の通り．

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x
		# print(self.parents)
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)