Problem:


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

Connected Components

  Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.

Input

  In the first line, two integer $n$ and $m$ are given. $n$ is the number of users in the SNS and $m$ is the number of relations in the SNS. The users in the SNS are identified by IDs $0, 1, ..., n-1$.

  In the following $m$ lines, the relations are given. Each relation is given by two integers $s$ and $t$ that represents $s$ and $t$ are friends (and reachable each other).

  In the next line, the number of queries $q$ is given. In the following $q$ lines, $q$ queries are given respectively. Each query consists of two integers $s$ and $t$ separated by a space character.

Output

  For each query, print "yes" if $t$ is reachable from $s$ through the social network, "no" otherwise.

Constraints

$2 \leq n \leq 100,000$

$0 \leq m \leq 100,000$

$1 \leq q \leq 10,000$

Sample Input

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

Sample Output

yes
yes
no



Sample input:
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3


Sample output:
yes
yes
no

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

NIL: int = -1


class DFS():
    def __init__(self, n, G, debug=False):
        self.n = n
        self.G = G
        self.color = [NIL] * n

        self.debug = debug
        self._debug_print_G()
        self._debug_print_color()

    def assign_color(self):
        id = 1                  # color の id
        for u in range(self.n):
            if self.color[u] == NIL:
                self._dfs(u, id)
                id += 1
        self._debug_print_color()

    def can_reach(self, s, t) -> ():
        """boolを返すっぽいけど、yes / no を　print するメソッド"""
        if self.color[s] == self.color[t]:
            print('yes')
        else:
            print('no')

    def _dfs(self, r: int, c: int):
        S = []                  # list をスタックとして使う
        S.append(r)
        self.color[r] = c
        while len(S) > 0:
            u = S.pop()
            for v in self.G[u]:
                if self.color[v] == NIL:
                    self.color[v] = c
                    S.append(v)

    def _debug_print_G(self):
        if not self.debug:
           return
        for i in range(self.n):
            print(f'{i}: {self.G[i]}')

    def _debug_print_color(self):
        if not self.debug:
           return
        print(f'color: {self.color}')


def main():
    n, m = [int(char) for char in input().split()]

    G = [[] for _ in range(n)]  # n要素の配列の配列
    for _ in range(m):
        s, t = [int(char) for char in input().split()]
        G[s].append(t)
        G[t].append(s)
    dfs = DFS(n, G)
    dfs.assign_color()

    q = int(input())
    for _ in range(q):
        s, t = [int(char) for char in input().split()]
        dfs.can_reach(s, t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Connected Components
from collections import defaultdict
import sys
sys.setrecursionlimit(1 << 25)  # 再起上限引き上げ

G = defaultdict(lambda: [])

# load data
N, M = list(map(int, input().split()))
color = {key: None for key in range(N)}  # 色というかグループ #intで表す #Noneは未訪問を示す
# graphをdefault dictで保持することにする。
for _ in range(M):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)

def dfs(node: int, co: int):
    if color[node] is not None:
        return
    color[node] = co
    for n in G[node]:
        dfs(n, co)
    return

# すべてのnodeを開始点としてdfsで領域わけしてみる
c = 1
for node in G.keys():
    dfs(node, c)  # 訪問済みだったら色を塗り替えないというないようはdfs関数内の処理で吸収できる
    c += 1

# 問題に回答していく
Q = int(input())
for _ in range(Q):
    s, t = list(map(int, input().split()))
    if ((color[s] is not None) and (color[t] is not None)) and (color[s] == color[t]):
        # s,tも友達がいて、かつ同じグループだったら
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())
E = [[] for _ in range(n)]

for _ in range(m):
	u, v = map(int, input().split())
	E[u].append(v)
	E[v].append(u)

color = [None]*n
cnt = 0 # now color

def dfs(v)->bool:
	if color[v] is not None: return False
	color[v] = cnt
	for nv in E[v]:
		if color[nv] is not None: continue
		dfs(nv)
	return True

for v in range(n):
	cnt += dfs(v)

q = int(input())
for _ in range(q):
	u, v = map(int, input().split())
	print("yes" if color[u]==color[v] else "no")

Submission status: Accepted

Solution code:
from collections import deque


def CC():
    id=0
    color=["white" for i in range(n)]
    for j in range(n):
        if color[j]=="white":
            color[j]="gray"
            queue=deque([j])

            while len(queue)!=0:
                u=queue.popleft()
                for i in M[u]:
                    if color[i]=="white":
                        color[i]="gray"
                        queue.append(i)
                color[u]=str(id)
            id +=1

    return color


n,m=map(int,input().split())
M=[[] for i in range(n)]
for i in range(m):
    p,q=map(int,input().split())
    M[p].append(q)
    M[q].append(p)

color=CC()

for i in range(int(input())):
    a,b=map(int,input().split())
    print("yes" if color[a]==color[b] else "no")

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
colors = {}
done = set()

for i in range(m):
    s, t = map(int, input().split())
    g[s].append(t)
    g[t].append(s)

# print(g)
color = 0

for i in range(n):
    if i in colors:
        continue
    done.clear()
    color += 1
    q = deque()
    q.append(i)

    while q:
        node = q.popleft()
        colors[node] = color
        for next in g[node]:
            if next not in done:
                done.add(next)
                q.append(next)

# print(colors)

Q = int(input())
qs = []
for i in range(Q):
    s, t = map(int, input().split())
    qs.append([s, t])

for i in range(len(qs)):
    if colors[qs[i][0]] == colors[qs[i][1]]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
from collections import deque


def bfs(adj_list, n):
    color = [None] * n
    color_count = 0
    searching = deque()
    for i in range(n):
        if color[i] is None:
            color_count += 1
            color[i] = color_count
            searching.append(i)
            while len(searching) > 0:
                start = searching.popleft()
                for end in adj_list[start]:
                    if color[end] is None:
                        color[end] = color_count
                        searching.append(end)
    return color


def dfs(adj_list, n):
    color = [None] * n
    color_count = 0
    searching = deque()
    for i in range(n):
        if color[i] is None:
            color_count += 1
            color[i] = color_count
            searching.append(i)
            while len(searching) > 0:
                start = searching.pop()
                for end in adj_list[start]:
                    if color[end] is None:
                        color[end] = color_count
                        searching.append(end)
    return color


def main():
    nm = input().split()
    n, m = list(map(int, nm))
    adj_list = [[] for _ in range(n)]
    for _ in range(m):
        st = input().split()
        s, t = list(map(int, st))
        adj_list[s].append(t)
        adj_list[t].append(s)
    color = dfs(adj_list, n)
    q = int(input())
    for _ in range(q):
        st = input().split()
        s, t = list(map(int, st))
        if color[s] == color[t]:
            print("yes")
        else:
            print("no")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lis=[[]for _ in range(n)]
for _ in range(m):
	s,t=map(int,input().split())
	lis[s].append(t)
	lis[t].append(s)
from collections import deque as dq
queue=dq([])
cnt=0
k=0
color=[-1]*n
while True:
	while k<n:
		if color[k]!=-1:
			k+=1
		else:
			break
	try:
		p=color[k:].index(-1)+k
	except:
		break
	queue.append(p)
	while queue:
		r=queue.popleft()
		color[r]=cnt
		for i in range(len(lis[r])):
			if color[lis[r][i]]==-1:
				queue.append(lis[r][i])
				color[lis[r][i]]=cnt
	cnt+=1
q=int(input())
for _ in range(q):
	s,t=map(int,input().split())
	if color[s]==color[t]:
		print("yes")
	else:
		print("no")

Submission status: Accepted

Solution code:

NIL = -1

def assignColor():
    id = 1
    for i in range(n):
        color[i] = NIL
    for u in range(n):
        if color[u] == NIL:
            dfs(u, id)
            id += 1

def dfs(r, c):
    S = []
    S.append(r)
    color[r] = c
    while S:
        u = S.pop()
        for v in (G[u]):
            if color[v] == NIL:
                color[v] = c
                S.append(v)


nums=list(map(int,input().split()))
n = nums[0]
m = nums[1]
G = []
color = [NIL] * n

for i in range(n):
    G.append(set())
    
for i in range(m):
    nodes=list(map(int,input().split()))
    G[nodes[0]].add(nodes[1])
    G[nodes[1]].add(nodes[0])

assignColor()

q = int(input())
for i in range(q):
    questions=list(map(int,input().split()))
    if color[questions[0]] == color[questions[1]]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    root = {i:i for i in range(n)}
    
    for i in range(m):
        s, t = map(int, input().split())
        
        r, c = s, 0
        while root[s] != s: s, c = root[s], c+1
        while root[t] != t: root[t], t = s, root[t]
        root[t] = s
        
        if c > 10: 
            while root[r] != s: root[r], r = s, root[r]
        
    for i in range(int(input())):
        s, t = map(int, input().split())
        
        while root[s] != s: s = root[s]
        while root[t] != t: t = root[t]
        
        if s == t: print('yes')
        else: print('no')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
class Union():
    def __init__(self, n):
        self.pre = [i for i in range(n)]
        self.rank = [1 for _ in range(n)]

    def union(self, a, b):
        aroot = self.find(a)
        broot = self.find(b)
        if aroot == broot:
            return
        if self.rank[aroot] < self.rank[broot]:
            aroot, broot = broot, aroot
        self.pre[broot] = self.pre[aroot]
        if self.rank[aroot] == self.rank[broot]:
            self.rank[aroot] += 1

    def find(self, n):
        while self.pre[n] != n:
            n = self.pre[n]
        return n

    def issame(self, a, b):
        if self.find(a) == self.find(b):
            return True
        return False

if __name__ == '__main__':
    m, n = map(int, sys.stdin.readline().split())
    union = Union(m)

    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        union.union(a, b)

    o = int(input())
    for _ in range(o):
        p, q = map(int, sys.stdin.readline().split())
        if union.issame(p, q):
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
import sys
def s():
 e=sys.stdin.readline
 n,m=map(int,e().split())
 P=[[]for _ in[0]*n]
 C=[0]*n
 k=0
 for _ in[0]*m:
  s,t=map(int,e().split());P[s]+=[t];P[t]+=[s]
 for i in range(n):
  k+=1
  if C[i]<1:
   s=[i];C[i]=k
   while s:
    u=s.pop()
    for v in P[u]:
     if C[v]<1:C[v]=k;s+=[v]
 for _ in[0]*int(e()):
  a,b=map(int,e().split())
  print(['no','yes'][C[a]==C[b]])
s()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


def depth_first_search(node, friend_list, color_list, color):
    color_list[node] = color
    # print(color_list)
    for friend in friend_list[node]:
        if color_list[friend] == -1:
            color_list = depth_first_search(friend, friend_list,\
                 color_list, color)
    return color_list
        

# f =  open('alds1_11_d-input3.txt', 'r')
# n_user, n_relation = list(map(int, f.readline().split()))
n_user, n_relation = list(map(int, input().split()))

friend_list = [[] for _ in range(n_user)]
for _ in range(n_relation):
    # user, friend = list(map(int, f.readline().split()))
    user, friend = list(map(int, input().split()))
    friend_list[user].append(friend)
    friend_list[friend].append(user)


color_list = [-1 for _ in range(n_user)]
color = 0
for user in range(n_user):
    if color_list[user] == -1:
        color_list = depth_first_search(user, friend_list,\
                color_list, color)
        color += 1

# n_question = int(f.readline())
n_question = int(input())
for _ in range(n_question):
    # user, friend = list(map(int, f.readline().split()))
    user, friend = list(map(int, input().split()))
    if color_list[user] == color_list[friend]:
        print('yes')
    else:
        print('no')
# f.close()

Submission status: Accepted

Solution code:
from collections import deque


n = 0
m = 0
M = None
color = None


def main():
    global n, m, M, color
    n, m = map(int, input().split(' '))

    M = [[] for _ in range(n)]
    color = [-1 for _ in range(n)]

    for _ in range(m):
        a, b = map(int, input().split(' '))
        M[a].append(b)
        M[b].append(a)

    num = 1
    for u in range(n):
        if color[u] == -1:
            dfs(u, num)
            num += 1

    k = int(input())
    for _ in range(k):
        a, b = map(int, input().split(' '))
        if color[a] == color[b]:
            print('yes')
        else:
            print('no')


def dfs(r, c):
    stack = deque()
    stack.append(r)
    color[r] = c
    while len(stack) > 0:
        u = stack.pop()
        for i in range(len(M[u])):
            v = M[u][i]
            if color[v] == -1:
                color[v] = c
                stack.append(v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_D

from collections import defaultdict
import sys
sys.setrecursionlimit(1 << 25)  # 再起上限引き上げ

G = defaultdict(lambda: [])

# load data
N, M = list(map(int, input().split()))
color = {key: None for key in range(N)}  # 色というかグループ #intで表す #Noneは未訪問を示す
# graphをdefault dictで保持することにする。
for _ in range(M):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)

# 離接リストをもとに、たどり着ける友達関係をグループ化する #(union findが使える気もするけどここではDFSで領域を探索していく)


def dfs(node: int, co: int):
    # 終了条件 #すでに訪問済みなら訪問しない
    if color[node] is not None:
        return
    # 処理
    color[node] = co
    # 探索
    for n in G[node]:
        dfs(n, co)
    return


# すべてのnodeを開始点としてdfsで領域わけしてみる
c = 1
for node in G.keys():
    dfs(node, c)  # 訪問済みだったら色を塗り替えないというないようはdfs関数内の処理で吸収できる
    c += 1


# 問題に回答していく
Q = int(input())
for _ in range(Q):
    s, t = list(map(int, input().split()))
    if ((color[s] is not None) or (color[t] is not None)) and (color[s] == color[t]):
        # s,tも友達がいて、かつ同じグループだったら
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

n,m=map(int,input().split())
G=[[]*n for i in range(n)]
color=[-1]*n
for i in range(m):
    v1,v2=map(int,input().split())
    G[v1].append(v2)
    G[v2].append(v1)


def dfs(v,c):
    color[v]=c
    for vi in G[v]:
        if color[vi]==-1:
            dfs(vi,i)


for i in range(n):
    if color[i]==-1:
        dfs(i,i)

q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    print('yes' if color[s]==color[t] else 'no')

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())

V =[deque([]) for _ in range(n)]
color = [0 for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)

friend = 1

def dfs(u,f):
    global color
    color[u] = f
    stack = []
    stack.append(u)
    while len(stack) != 0:
        now = stack[-1]
        # print(now,V,color)
        if len(V[now]) != 0:
            nb = V[now].popleft()
            if color[nb] == 0:
                stack.append(nb)
                color[nb] = f
        else :
            stack.pop()

# print("")

for i in range(n):
    if color[i]==0:
        dfs(i,friend)
        friend += 1

# print("")
# print(V)
# print(color)
q = int(input())
for _ in range(q):
    a,b = map(int,input().split())
    if color[a] == color[b]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from collections import deque

def main():
    n, m = map(int, input().strip().split())
    nei = [[] for _ in range(n)]
    for _ in range(m):
        s, t = map(int, input().strip().split())
        nei[s].append(t)
        nei[t].append(s)

    nodes = [-1] * n
    color = 1
    for i in range(n):
        if nodes[i] > 0:
            continue
        d = deque()
        d.append(i)
        # print(nei)
        while len(d) != 0:
            k = d.popleft()
            nodes[k] = color
            for j in nei[k]:
                if nodes[j] == -1:
                    d.append(j)
            # print(len(d))
        color += 1

    q = int(input().strip())
    for _ in range(q):
        s, t = map(int, input().strip().split())
        if nodes[s] == nodes[t]:
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def dfs(r: int, c: int) -> None:
	S = deque()
	S.append(r)
	color[r] = c
	while S:
		u = S.pop()
		for v in G[u]:
			if color[v] == None:
				color[v] = c
				S.append(v)

def assignColor():
	id: int = 1
	for u in range(n):
		if color[u] == None:
			dfs(u, id)
			id += 1


if __name__ == "__main__":
	n, m = map(int, input().split())
	G = [[] for _ in range(n)]
	for _ in range(m):
		u, v = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	color = [None for _ in range(n)]
	assignColor()
	q = int(input())
	for _ in range(q):
		u, v = map(int, input().split())
		if color[u] == color[v]:
			print("yes")
		else:
			print("no")

Submission status: Accepted

Solution code:
# ALDS1_11_D Connected Components
import sys
import queue


sys.setrecursionlimit(1000000)

def check(adj, foot_print):
    n = len(foot_print)
    que = queue.Queue()
    num = 0
    for i in range(n):
        if foot_print[i] == 0:
            num += 1
            que.put(i)
            foot_print[i] = num
            bfs(adj, que, foot_print, num)


def bfs(adj, que, foot_print, num):
    if not que.empty():
        now = que.get()
        for i in adj[now]:
            if foot_print[i] == 0:
                foot_print[i] = num
                que.put(i)
        bfs(adj, que, foot_print, num)
    else:
        return


def main():
    n, m = map(int, sys.stdin.readline().strip().split())
    adj_list = [[] for _ in range(n)]
    for i in range(m):
        s, t = map(int, sys.stdin.readline().strip().split())
        adj_list[s].append(t)
        adj_list[t].append(s)

    foot_print = [0] * n
    check(adj_list, foot_print)

    q = int(input())
    for i in range(q):
        s, t = map(int, sys.stdin.readline().strip().split())
        if foot_print[s] == foot_print[t]:
            print('yes')
        else:
            print('no')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

class Union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):# 頂点xのroot(根)頂点を見つける
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):#頂点xと頂点yを繋ぐ辺を追加
        x=self.find_root(x)
        y=self.find_root(y)

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def same(self,x,y):#頂点xと頂点yが連結であるか判定
        return self.find_root(x)==self.find_root(y)

    def count(self,x):#頂点xが属する木のサイズ
        return -self.root[self.find_root(x)]

n,m=map(int,input().split())
gragh=Union_find(n+1)
for i in range(m):
    a,b=map(int,input().split())
    gragh.unite(a,b)
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    print("yes" if gragh.same(s,t) else "no")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    link[u].append(v)
    link[v].append(u)
group = [-1] * n
gid = 0
for i in range(n):
    if group[i] != -1:
        continue
    stack = [i]
    group[i] = gid
    while stack:
        u = stack.pop()
        for v in link[u]:
            if group[v] == -1:
                group[v] = gid
                stack.append(v)
    gid += 1
q = int(input())
for _ in range(q):
    u, v = map(int, input().split())
    print('yes' if group[u] == group[v] else 'no')

Submission status: Accepted

Solution code:
class UnionSet:
    def __init__(self, num_node: int) -> None:
        self.size = [1] * num_node
        self.id = [i for i in range(num_node + 1)]

    def get_root(self, i: int) -> int:
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i

    def is_connected(self, node1: int, node2: int) -> bool:
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1: int, node2: int) -> None:
        i, j = self.get_root(node1), self.get_root(node2)
        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]


if __name__ == "__main__":
    num_users, num_relations = map(lambda x: int(x), input().split())
    union_set = UnionSet(num_users)

    for _ in range(num_relations):
        user1, user2 = map(lambda x: int(x), input().split())
        union_set.unite(user1, user2)

    num_questions = int(input())
    for _ in range(num_questions):
        user1, user2 = map(lambda x: int(x), input().split())
        if union_set.is_connected(user1, user2):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,m=map(int,input().split())
graph=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    if reached[v]:
        reached[v]=0
        ll.add(v)
        for i in range(len(graph[v])):
            dfs(graph[v][i])

reached=[1]*n
ans=[[] for _ in range(n)]

for j in range(n):
    ll=set()
    dfs(j)
    if ll:
        for s in ll:
            ans[s]=ll

q=int(input())
ab=[]
for i in range(q):
    a,b=map(int,input().split())
    ab.append([a,b])

for i in range(q):
    a,b=ab[i][0],ab[i][1]
    if b in ans[a]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""

"""

import sys
sys.setrecursionlimit(1000000)


n,m=[int(i) for i in input().split()]
graph=[[] for i in range(n)]

for i in range(m):
    relation=[int(j) for j in input().split()]
    graph[relation[0]].append(relation[1])
    graph[relation[1]].append(relation[0])


check=[0 for i in range(n)]
rabel=0
stack=[]

#深さ優先探索
def dfs(graph,i):
    global stack
    global n
    global rabel

    if check[i]==0:

        #行った足跡をつける
        check[i]=rabel

        #今いる場所の情報
        now=graph[i]

        #スタックに入れる
        stack.append(now)

        #今いる場所から到達できる地点のうち、まだ行っていないとこ全部でdfs
        for j in now:
            if check[j]==0:
                dfs(graph,j)

        stack.pop()

for i in range(n):
    if check[i]==0:
        rabel+=1
        dfs(graph,i)
# print(check)



num=int(input())
for i in range(num):
    a,b=[int(j) for j in input().split()]
    if check[a]==check[b]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
class ConnectedComponents():
    def __init__(self, n):
        self.size = [1] * n
        self.id = [i for i in range(n + 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 relations(self, s, t):
        s_root = self.root(s)
        t_root = self.root(t)

        if s_root == t_root: 
            return

        if self.size[s_root] < self.size[t_root]:
            self.id[s_root] = t_root
            self.size[t_root] += self.size[s_root]
        else:
            self.id[t_root] = s_root
            self.size[s_root] += self.size[t_root]

    def find(self, s, t):
        return self.root(s) == self.root(t)

# INPUT
n, m = map(int, input().split())

CC = ConnectedComponents(n)

for _ in range(m):

    s, t = map(int, input().split())

    CC.relations(s, t)

# QUESTION
q = int(input())

for _ in range(q):

    s, t = map(int, input().split())

    if CC.find(s, t):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

friend = [ [] for _ in range(n) ]

for _ in range(m):
    s, t = map(int, input().split())
    friend[s].append(t)
    friend[t].append(s)

flag = [0] * n
group = 0

# def dfs(u):
#    for v in friend[u]:
#        if flag[v] == 0:
#            flag[v] = group
#            dfs(v)

for i in range(n):
    if flag[i] == 0:
        group += 1
        flag[i] = group
        # dfs(i)
        
        stack = [i]
        
        while stack:
            u = stack.pop()
            for v in friend[u]:
                if flag[v] == 0:
                    flag[v] = group
                    stack.append(v)

q = int(input())

for _ in range(q):
    s, t = map(int, input().split())
    if flag[s] == flag[t]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
# がんばったけどTLE
n, m = [int(i) for i in input().split()]
G = [[] for i in range(n)]
for mi in range(m):
    u, v = [int(i) for i in input().split()]
    G[u].append(v)
    G[v].append(u)
NIL = -1
Group = [NIL for i in range(n)]
num = 0
S = []
D = []


def DFS(id, u):
    S.append(u)
    Group[u] = id
    while S != []:
        for v in G[u]:
            if Group[v] == NIL:
                S.append(v)
                Group[v] = id
        u = S.pop()

'''
for num in range(n):
    if NIL not in Group:
        break
    else:
        u = Group.index(NIL)
        DFS(num, u)
'''
num = 0
q = int(input())
for qi in range(q):
    s, t = [int(i) for i in input().split()]
    if Group[s] == NIL:
        DFS(num, s)
        num += 1
    if Group[s] == Group[t]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs():
    while len(bfs_q)>0:
        u = bfs_q.popleft()
        for v in adj_list[u]:
            if flag_list[v] == 0:
                group_list[v] = g
                flag_list[v] = 1
                bfs_q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n, m = map(int, input().split())
    adj_list = [[] for _ in range(n)]
    for _ in range(m):
        s, t = list(map(int, input().split()))
        adj_list[s].append(t)
        adj_list[t].append(s)

    group_list = [0]*n
    flag_list = [0]*n # 0: 未到達, 1: 処理中, 2: 完了
    bfs_q = deque([])
    g = 0
    for i in range(n):
        if flag_list[i] == 0:
            group_list[i] = g
            flag_list[i] = 1
            bfs_q.append(i)
            bfs()
            g += 1

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        if group_list[s] == group_list[t]:
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
*p, = range(n)
def root(s):
    if s == p[s]:
        return p[s]
    p[s] = s = root(p[s])
    return s
def unite(a, b):
    aa = root(a);bb = root(b)
    if aa < bb:
        p[bb] = aa
    else:
        p[aa] = bb
        
for i in range(m):
    s, t = map(int, input().split())
    unite(s, t)
N = int(input())
*_, = map(root, range(n))

ans = []
for i in range(N):
    s, t = map(int, input().split())
    ans.append('yes' if p[s] == p[t] else 'no')
print('\n'.join(ans))

Submission status: Accepted

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

rank = [1]*n
dad = [i for i in range(n)]

def find(a):
    if a == dad[a]:
        return a
    else:
        dad[a] = find(dad[a])
        return dad[a]

for _ in range(m):
    a,b = map(int,input().split(" "))

    #find parents
    aP = find(a)
    bP = find(b)
    if aP == bP:
        continue

    aR = rank[aP]
    bR = rank[bP]

    if aR >= bR:
        dad[bP] = aP
        if rank[aP] == rank[bP]:
            rank[aP] += 1
            rank[bP] = rank[aP]
    else:
        dad[aP] = bP
        if rank[aP] == rank[bP]:
            rank[bP] += 1
            rank[aP] = rank[bP]

qN = int(input())
for _ in range(qN):
    a,b = map(int,input().split(" "))
    if find(a) == find(b):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
import sys
sys.setrecursionlimit(1000000)
c_list = {}
# 辞書の初期化
for node in range(n):
    c_list[node] = []

for _ in range(m):
    a, b = map(int, input().split())
    c_list[a].append(b)
    c_list[b].append(a)

colors = {}


# 色を割り当てていく
def dfs(node, c):
    if node not in colors:
        colors[node] = c
        for next in c_list[node]:
            dfs(next, c)


# stackでも書きたい
# 色の割当が間違っている
def assignColor():
    c = 0
    for node in c_list:
        if node not in colors:
            dfs(node, c)
            c += 1


def checkColor(u, v):
    if colors[u] == colors[v]:
        print('yes')
    else:
        print('no')


assignColor()
k = int(input())
for _ in range(k):
    u, v = map(int, input().split())
    checkColor(u, v)