Problem:


Community Integration

Problem

N個の村がある。それぞれの村には1からNまでの番号がついている。昨今の合併ブームにより、いくつかの村が合併されることになった。合併された2つ以上の村は新しい1つの市となり、どの村とも合併されない村は村のままである。

あなたは、ある2つの村が合併後に同じ市になる、という情報を複数与えられる。その情報の組み合わせによって、3つ以上の村が1つの市になることもありうる。

合併後に同じ市になる村同士の情報が与えられたとき、合併後の市の数と村の数の差の絶対値を出力せよ。

Input

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

N M
a1 b1
a2 b2
...
ai bi
...
aM bM

1行目に村の数Nと合併についての情報の数Mが空白区切りで与えられる。

2行目からM+1行目に、合併についての情報を表す２つの整数aiとbiが空白区切りで与えらる。各情報はai番目の村とbi番目の村が合併後に同じ市になることを示す。ただし、ai=biを満たすような入力は与えられない。

Constraints

	
1 ≤ N ≤ 1,000

	
0 ≤ M ≤ 100

	
1 ≤ ai ≤ N

	
1 ≤ bi ≤ N

Output

村の数と市の数の差の絶対値を1行に出力せよ。

Sample Input 1

3 1
1 2

Sample Output 1

0

Sample Input 2

4 2
1 4
2 3

Sample Output 2

2

Sample Input 3

5 0

Sample Output 3

5

Sample Input 4

3 3
1 2
2 3
3 1

Sample Output 4

1

このケースではすべての村が1つの市に合併されることを表し、その市の中で合併される2つの村をつなぐつなぎ方の全通りが入力として与えられている。

Sample Input 5

3 2
1 2
2 3

Sample Output 5

1

このケースでは合併される3つの村をつなぐつなぎ方の全通りが入力として与えられているわけではないが、つながっている村をたどればすべての村にたどり着くことができるので、すべての村が一つの市に合併される。

Sample Input 6

5 4
1 2
2 3
3 4
4 5

Sample Output 6

1

Sample Input 7

10 5
3 4
1 2
9 6
2 6
2 9

Sample Output 7

2



Sample input:
3 1
1 2


Sample output:
0

Submission status: Wrong Answer

Solution code:
[m,n] = map(int,input().split())

def find(v,cs):
    for c in cities:
        if v in c:
            return (True,c)
    return (False,set([v]))

cities = []
for _ in range(n):
    [a,b] = map(int,input().split())

    (ra,fa) = find(a,cities)
    (rb,fb) = find(b,cities)

    mg = fa | fb

    print(fa)

    if ra:
        cities.remove(fa)
    else:
        m = m - 1
    if rb:
        if fa != fb:
            cities.remove(fb)
    else:
        m = m - 1
    cities.append(mg)

print(abs(m-len(cities)))

Submission status: Accepted

Solution code:
# AOJ 1576: Community Integration
# Python3 2018.7.13 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

N, M = map(int, input().split())
u = UnionSet(N+1)
f = [0]*(N+1)
for i in range(M):
	a, b = map(int, input().split())
	u.unite(a, b)
for i in range(1, N+1): f[u.root(i)] += 1
a = b = 0
for i in range(1, N+1):
	if f[i] == 1: a += 1
	elif f[i] > 1: b += 1
print(abs(a-b))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array


class UnionFind(object):

    def __init__(self, number_of_nodes, typecode="L"):
        self.typecode = typecode
        self.par = array.array(typecode, range(number_of_nodes))
        self.rank = array.array(typecode, (0 for i in range(number_of_nodes)))

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n, "I")
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.unite(a, b)
    city_representatives = set()
    num_cities_and_villages = 0
    for i in range(n):
        rep = uf.root(i)
        if i == rep:
            num_cities_and_villages += 1
        else:
            city_representatives.add(rep)
    num_cities = len(city_representatives)
    answer = abs(num_cities_and_villages - 2 * num_cities)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
[m,n] = map(int,input().split())

def find(v,cs):
    for c in cities:
        if v in c:
            return (True,c)
    return (False,set([v]))

cities = []
for _ in range(n):
    [a,b] = map(int,input().split())

    (ra,fa) = find(a,cities)
    (rb,fb) = find(b,cities)

    mg = fa | fb

    if ra:
        cities.remove(fa)
    else:
        m = m - 1
    if rb:
        if fa != fb:
            cities.remove(fb)
    else:
        m = m - 1
    cities.append(mg)

print(abs(m-len(cities)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
q = []
for _ in range(m):
    a, b = map(int, input().split())
    i, j = -1, -1
    for k in range(len(q)):
        if i == -1:
            if a in q[k]:
                i = k
        if j == -1:
            if b in q[k]:
                j = k
        if i >= 0 and j >= 0:
            break
    if i >= 0:
        if j >= 0:
            if i != j:
                q[i] |= q[j]
                q.pop(j)
        else:
            q[i].add(b)
    elif j >= 0:
        q[j].add(a)
    else:
        q.append(set([a, b]))
print(abs(n - sum([len(i) for i in q]) - len(q)))

Submission status: Accepted

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

def get_par(x):
    if x == parent[x]:return x
    parent[x] = get_par(parent[x])
    return parent[x]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    pa, pb = get_par(a), get_par(b)
    parent[pb] = pa

city_dic = set()
village_cnt = 0
for i in range(n):
    pi = get_par(i)
    if i == pi:village_cnt += 1
    else:city_dic.add(pi)

print(abs(2 * len(city_dic) - village_cnt))