Problem:


Score : 800 points

Problem Statement

Takahashi has received an undirected graph with N vertices, numbered 1, 2, ..., N.
The edges in this graph are represented by (u_i, v_i).
There are no self-loops and multiple edges in this graph.

Based on this graph, Takahashi is now constructing a new graph with N^2 vertices, where each vertex is labeled with a pair of integers (a, b) (1 \leq a \leq N, 1 \leq b \leq N).
The edges in this new graph are generated by the following rule:

Span an edge between vertices (a, b) and (a', b') if and only if both of the following two edges exist in the original graph: an edge between vertices a and a', and an edge between vertices b and b'.

How many connected components are there in this new graph?

Constraints

2 \leq N \leq 100,000

0 \leq M \leq 200,000

1 \leq u_i < v_i \leq N

There exists no pair of distinct integers i and j such that u_i = u_j and v_i = v_j.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
:
u_M v_M

Output

Print the number of the connected components in the graph constructed by Takahashi.

Sample Input 1

3 1
1 2

Sample Output 1

7

The graph constructed by Takahashi is as follows.

Sample Input 2

7 5
1 2
3 4
3 5
4 5
2 6

Sample Output 2

18



Sample input:
3 1
1 2


Sample output:
7

Submission status: Accepted

Solution code:
'''
写経
https://youtu.be/cJ-WjtA34GQ?t=1899
https://atcoder.jp/contests/agc011/submissions/1157055
http://noshi91.hatenablog.com/entry/2018/04/17/183132
https://camypaper.bitbucket.io/2016/12/18/adc2016/
'''


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


N, M = map(int, input().split())
uf = UnionFind(2 * N)  # 全頂点 * 2(赤, 青の塗り分け)
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    uf.unite(u, N + v)  # u, v: 赤で塗る / N + u, N + v: 青で塗る
    uf.unite(N + u, v)  # 隣り合う頂点を赤, 青または青, 赤で着色したものとして, 集合に加える(二部グラフならば矛盾※が出ない)

    # print(uf.v)

alone = 0
bi = 0
unko = 0

for u in range(N):
    if uf.root(u) or uf.root(N + u): # 根になりうる場合, 単独/二部はどちらもTrue, 二部グラフではない場合は, どちらかの頂点がTrue
        if uf.size(u) == 1: # 単独ならu, N + uのどちらも単独なので, 片方調べればよい
            alone += 1
        elif uf.same(u, N + u):  # ※同じ頂点の赤, 青が同じ集合にあれば塗り分けについて矛盾しており, 二部グラフではない
            unko += 1
        else:
            bi += 1  # 二部グラフ

ans = 0
ans += alone * N
ans += N * alone
ans -= alone * alone
ans += bi * bi * 2
ans += bi * unko
ans += unko * bi
ans += unko * unko

print(ans)

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/agc011/submissions/1157055

class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

    def find(self, x):
        if self.v[x] < 0:
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.v[self.find(x)]


N, M = map(int, input().split())
uf = UnionFind(2 * N)
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    uf.unite(u, N + v)
    uf.unite(N + u, v)

alone = 0
bi = 0
unko = 0

for u in range(N):
    if uf.root(u) or uf.root(N + u):
        if uf.size(u) == 1:
            alone += 1
        elif uf.same(u, N + u):
            unko += 1
        else:
            bi += 1

ans = 0
ans += alone * N
ans += N * alone
ans -= alone * alone
ans += bi * bi * 2
ans += bi * unko
ans += unko * bi
ans += unko * unko

print(ans)

Submission status: Accepted

Solution code:
import sys
n, m=map(int, raw_input().split())
sys.setrecursionlimit(n+1000)
adj=[[] for i in range(n+1)]
for i in range(m):
	u, v=map(int, raw_input().split())
	adj[u].append(v)
	adj[v].append(u)
isolated_cnt=0
bipartite_cnt=0
other_cnt=0
color=[0]*(n+1)
def dfs(cur):
	global ok
	for to in adj[cur]:
		if not color[to]:
			color[to]=3-color[cur]
			dfs(to)
		else:
			if color[to]!=3-color[cur]:
				ok=False
for i in range(1, n+1):
	if adj[i]:
		if not color[i]:
			color[i]=1
			ok=True
			dfs(i)
			if ok:
				bipartite_cnt+=1
			else:
				other_cnt+=1
	else:
		isolated_cnt+=1
print>>sys.stderr, isolated_cnt, bipartite_cnt, other_cnt
print isolated_cnt*n*2-isolated_cnt*isolated_cnt+bipartite_cnt*(bipartite_cnt*2+other_cnt)+other_cnt*(bipartite_cnt+other_cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			s,f=[(i,1)],True
			while len(s):
				u,col=s.pop()		
				if vis[u]:
					f&=(vis[u]==col)
					continue
				vis[u]=col
				for i in g[u]:
					s+=[(i,3-col)]
			cb+=f
			cc+=f^1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * m)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        dat[ui] -= 1
        dat[vi] -= 1
        u = dat[ui]
        v = dat[vi]
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = deque()
    done = [0] * n
    pu = q.append
    po = q.popleft
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if not done[z]:
                    done[z] = 3 - done[x]
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        pa = 0
        for x in nu:
            sd += deg[x]
            y = la[x]
            while y is not None:
                z = dat[y]
                if done[x] == done[z]:
                    pa = 1
                y = xt[y]
        if sd == 0:
            so += 1
        elif pa:
            lo += 1
        else:
            tr += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()

Submission status: Runtime Error

Solution code:
import sys
n, m=map(int, raw_input().split())
adj=[[] for i in range(n+1)]
for i in range(m):
	u, v=map(int, raw_input().split())
	adj[u].append(v)
	adj[v].append(u)
isolated_cnt=0
bipartite_cnt=0
other_cnt=0
color=[0]*(n+1)
def dfs(cur):
	for to in adj[cur]:
		if not color[to]:
			color[to]=3-color[cur]
			if not dfs(to):
				return False
		else:
			if color[to]!=3-color[cur]:
				return False
	return True
for i in range(1, n+1):
	if adj[i]:
		if not color[i]:
			color[i]=1
			if dfs(i):
				bipartite_cnt+=1
			else:
				other_cnt+=1
	else:
		isolated_cnt+=1
print>>sys.stderr, isolated_cnt, bipartite_cnt, other_cnt
print isolated_cnt*n*2-isolated_cnt*isolated_cnt+bipartite_cnt*(bipartite_cnt*2+other_cnt)+other_cnt*(bipartite_cnt+other_cnt)

Submission status: Runtime Error

Solution code:
import sys

class TailRecurseException:
	def __init__(self, args, kwargs):
		self.args = args
		self.kwargs = kwargs

def tail_call_optimized(g):
	def func(*args, **kwargs):
		f = sys._getframe()
		if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
			raise TailRecurseException(args, kwargs)
		else:
			while 1:
				try:
					return g(*args, **kwargs)
				except TailRecurseException, e:
					args = e.args
					kwargs = e.kwargs
	func.__doc__ = g.__doc__
	return func

n,m=map(int,raw_input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,raw_input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+5),0,0,0
g=[[] for i in range(n+5)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

class U():
    def __init__(self):
        self.live = [True] * (N ** 2)
    def _connect(self, i, j):
        if self.live[i]:
            self.live[i] = False
        else:
            self.live[j] = False
    def connect(self, e1, e2):
        a1, a2 = e1
        b1, b2 = e2
        self._connect(a1 * N + b1, a2 * N + b2)
        self._connect(a1 * N + b2, a2 * N + b1)
    def count(self):
        return sum(self.live)

u = U()

edges = []
for i in range(M):
    new_edge = list(map(int, input().split()))
    new_edge[0] -= 1
    new_edge[1] -= 1
    edges.append(new_edge)
    for edge in edges:
        u.connect(new_edge, edge)

print(u.count())

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

class UF():
    def __init__(self):
        self.live = [True] * (N ** 2)
    def _connect(self, i, j):
        if self.live[i]:
            self.live[i] = False
        else:
            self.live[j] = False
    def connect(self, e1, e2):
        a1, a2 = e1
        b1, b2 = e2
        self._connect(a1 * N + b1, a2 * N + b2)
        self._connect(a1 * N + b2, a2 * N + b1)
    def count(self):
        return sum(self.live)

uf = UF()

edges = []
for i in range(M):
    new_edge = list(map(int, input().split()))
    new_edge[0] -= 1
    new_edge[1] -= 1
    edges.append(new_edge)
    for edge in edges:
        uf.connect(new_edge, edge)

print(uf.count())
print(uf.live)

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * n)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        dat[ui] -= 1
        dat[vi] -= 1
        u = dat[ui]
        v = dat[vi]
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = deque()
    done = [0] * n
    pu = q.append
    po = q.popleft
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if not done[z]:
                    done[z] = 1
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        for x in nu:
            sd += deg[x]
        if sd == 0:
            so += 1
        elif sd == len(nu) * 2 - 2:
            tr += 1
        else:
            lo += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * n)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        u = dat[ui] - 1
        v = dat[vi] - 1
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = []
    done = [0] * n
    pu = q.append
    po = q.pop
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y] - 1
                if not done[z]:
                    done[z] = 1
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        for x in nu:
            sd += deg[x]
        if sd == 0:
            so += 1
        elif sd == len(nu) * 2 - 2:
            tr += 1
        else:
            lo += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()