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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)


class LinkedList:
    def __init__(self, n):
        self.n = n
        self.ll = [[] for _ in range(self.n)]

    def link(self, u, v, direction=False):
        self.ll[u].append(v)
        if not direction:
            self.ll[v].append(u)

    def dfs(self):
        self.cc = [None] * self.n

        color = 1
        for u in range(self.n):
            if not self.cc[u]:
                self.dfs_visit(u, color)
                color += 1

    def dfs_visit(self, u, color):
        self.cc[u] = color
        for v in self.ll[u]:
            if not self.cc[v]:
                self.dfs_visit(v, color)

    def check(self, u, v):
        if self.cc[u] == self.cc[v]:
            print('yes')
        else:
            print('no')


if __name__ == '__main__':
    n, m = map(int, input().split())
    ll = LinkedList(n)

    for _ in range(m):
        u, v = map(int, input().split())
        ll.link(u, v)
    ll.dfs()

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        ll.check(u, v)

Submission status: Accepted

Solution code:
import sys


class UnionFind:
    def __init__(self, node_size):
        self._node = node_size
        self.par = [i for i in range(self._node)]
        self.rank = [0] * self._node
        self.size = [1] * self._node

    def find(self, ver):
        if self.par[ver] == ver:
            return ver
        else:
            self.par[ver] = self.find(self.par[ver])
            return self.par[ver]

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.rank[ver1] < self.rank[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        self.size[ver1] += self.size[ver2]
        if self.rank[ver1] == self.rank[ver2]:
            self.rank[ver1] += 1

    def size(self, ver):
        ver = self.find(ver)
        return self.size[ver]

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        uf.unite(s, t)
    q = int(sys.stdin.readline())
    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())
        if uf.same(s, t):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
import sys


class UnionFind:
    def __init__(self, node_size):
        self._node = node_size
        self.par = [i for i in range(self._node)]
        self.rank = [0] * self._node

    def find(self, ver):
        if self.par[ver] == ver:
            return ver
        else:
            self.par[ver] = self.find(self.par[ver])
            return self.par[ver]

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.rank[ver1] < self.rank[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        if self.rank[ver1] == self.rank[ver2]:
            self.rank[ver1] += 1

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        uf.unite(s, t)
    q = int(sys.stdin.readline())
    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())
        if uf.same(s, t):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
from collections import deque
n,m = [int(i) for i in input().split()]
F = [{} for i in range(n)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
DP = [0 for i in range(n)]
c = 1
d = deque()
for i in range(n):
    if not DP[i]:
        d.append(i)
    while(len(d)>0):
        tmp = d.pop()
        DP[tmp] = c
        for i in F[tmp]:
            if not DP[i]:
                d.append(i)
    c+=1

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

Submission status: Accepted

Solution code:
from collections import deque
n,m = [int(i) for i in input().split()]
F = [{} for i in range(n)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
DP = [0 for i in range(n)]
c = 1
d = deque()
for i in range(n):
    if DP[i]:
        continue
    else:
        d.append(i)
    while(len(d)>0):
        tmp = d.pop()
        DP[tmp] = c
        for i in F[tmp]:
            if not DP[i]:
                d.append(i)
    c+=1

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

Submission status: Accepted

Solution code:
from collections import deque


user_num,rer_num=map(int,input().split())
graph=[[] for loop in range(user_num)]

for loop in range(rer_num):
    user1,user2=map(int,input().split())
    graph[user1].append(user2)
    graph[user2].append(user1)

#group[user1]はuser1が属するグループ.同じグループに属するuser同士は互いに到達可能
group=[-1]*user_num

que=deque([])
que.append(0)
tmp_group=0
for user in range(user_num):
    if(group[user]==-1):
        que.append(user)
        group[user]=tmp_group
        while(1):
            user1=que.popleft()
            for user2 in graph[user1]:
                if(group[user2]==-1):
                    que.append(user2)
                    group[user2]=tmp_group
            if(len(que)==0):
                tmp_group+=1
                break

for loop in range(int(input())):
    user1,user2=map(int,input().split())
    if(group[user1]==group[user2]):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from collections import deque
 
n, m = map(int, input().split())

adj = [[] for _ in range(n)] # adjacent list

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

c = ['w']*n # color of each vertex
con = [0]*n
cnt = 0


def BFS_visit(s):
    global c
    global cnt
    global con
    
    c[s] = 'g'
    con[s] = cnt
    
    Q = deque()
    Q.append(s)
    while Q:
        u = Q.popleft()
        for v in adj[u]:
            if c[v] == 'w':
                c[v] = 'g'
                con[v] = cnt
                Q.append(v)
        c[u] = 'b'
        
for u in range(n):
    if c[u] == 'w':
        cnt += 1
        BFS_visit(u)
        
        
q = int(input())
for _ in range(q):
    u, v = map(int, input().split())
    ans = "yes" if (con[u] == con[v]) else "no"
    print(ans)

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    s,t=MAP()
    nodes[s].append(t)
    nodes[t].append(s)

group=[-1]*N
def rec(u, root):
    if group[u]!=-1:
        return
    group[u]=root
    for v in nodes[u]:
        rec(v, root)

for i in range(N):
    rec(i, i)

Q=INT()
for _ in range(Q):
    s,t=MAP()
    if group[s]==group[t]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

# Union-Find木
class UnionFind:
    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (n+1)

    # 根の検索(グループ番号と言えなくもない)
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # あるノードの属する集合のノード数
    def get_size(self, x):
        return self.size[self.find(x)]

    # 木かどうかの判定
    def is_tree(self, x):
        return self.tree[self.find(x)]

    # 集合の数
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N,M=MAP()
uf=UnionFind(N)
for i in range(M):
    s,t=MAP()
    uf.union(s, t)

Q=INT()
for _ in range(Q):
    s,t=MAP()
    if uf.same(s, t):
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

for i in range(m):
    s, t = map(int, input().split())
    relations[s] += [t]
    relations[t] += [s]
friend_id = [None] * n
for s, t in enumerate(relations):
    if t:
        queue = [s]
        while len(queue):
            k = queue.pop()
            friend_id[k] = s
            queue += relations[k]
            relations[k] = []

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

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)

color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1


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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

def set_color(i, ci, e, color):
    color[i] = ci
    next_i = set(e[i])
    while len(next_i):
        s = next_i.pop()
        if color[s] != ci:
            color[s] = ci
            next_i.update(e[s])


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

e = [set() for i in range(n)]
color = [None] * n

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

ci = 0
for i in range(n):
    if color[i] == None:
        set_color(i, ci, e, color)
        ci += 1

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

Submission status: Accepted

Solution code:
Group = [None] * 100001
Edge  = [None] * 100001

def DFS(item, group):
    S = []
    S.append(item)
    Group[item] = group
    while (len(S) != 0):
        S_top = S.pop()
        for link in Edge[S_top]:
            if Group[link] == 0:
                Group[link] = group
                S.append(link)

n, m = map(int, raw_input().split())
for i in xrange(n):
    Edge[i] = []
    Group[i] = 0

for i in xrange(m):
    s, t = map(int, raw_input().split())
    Edge[s].append(t)
    Edge[t].append(s)

group = 1
for i in xrange(n):
    if Group[i] == 0:
        DFS(i, group)
        group = group + 1

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1

Submission status: Accepted

Solution code:
def set_sns():
	sns[i] = ci
	next_i = set(e[i])
	while len(next_i):
		s = next_i.pop()
		if sns[s] != ci:
			sns[s] = ci
			next_i.update(e[s])
			
n, m = map(int, raw_input().split())

e = [set() for i in range(n)]
sns = [None] * n

for i in range(m):
	s, t = map(int, raw_input().split())
	e[s].add(t)
	e[t].add(s)

ci = 0
for i in range(n):
	if sns[i] == None:
		set_sns()
		ci += 1

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

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
 
 
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().strip().split(' '))
follow = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    follow[s].append(t)
    follow[t].append(s)
 
color = {}
c = 0

for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in follow[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
 
 
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

Solution code:
x,y = map(int,raw_input().strip().split(' '))
follow = [[] for i in range(x)]
for i in range(y):
    s,t = map(int,raw_input().strip().split(' '))
    follow[s].append(t)
    follow[t].append(s)
 
color = {}
c = 0

for i in range(x):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in follow[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
 
 
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
  s,t = map(int,raw_input().strip().split(' '))
  graph[s].append(t)
  graph[t].append(s)
color = {}
c = 0
for i in range(n):
  if not i in color:
     que = [i]
     color[i] = c
     while len(que) > 0:
       u = que[0]
       for v in graph[u]:
          if not v in color:
             color[v] = c
             que.append(v)
       del que[0]
     c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
   s,t = map(int,raw_input().strip().split(' '))
   if color[s] == color[t]:
     print 'yes'
   else:
     print 'no'

Submission status: Accepted

Solution code:
from collections import deque

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

color = [-1] * n
G = [ deque([]) for _ in xrange(n)]

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

    return 

def assignColor():
    id_ = 1
    for u in xrange(n):
        if color[u] == -1:
            dfs(u,id_)
            id_ += 1
    return

def main():
    for i in xrange(m):
        a = map(int, raw_input().split())
        #print a,a[1],G[a[1]],color[9]
        G[a[0]].append(a[1])
        G[a[1]].append(a[0])

    assignColor()
    
    q = int(raw_input())
    for i in xrange(q):
        a = map(int, raw_input().split())
        if color[a[0]] == color[a[1]]:
            print 'yes'
        else:
            print 'no'

    return 0

main()

Submission status: Accepted

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


class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if 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 same(self, x, y):
        return self.find(x) == self.find(y)

V, E = map(int, input().split())
uf = UnionFindTree(V)
for _ in range(E):
    uf.unite(*map(int, input().split()))
for _ in range(int(input())):
    print('yes' if uf.same(*map(int, input().split())) else 'no')

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    edge[s].append(t)
    edge[t].append(s)

group = [-1] * V
cnt = 0
for i in range(V):
    if group[i] == -1:
        group[i] = cnt
        stack = [i]
        while stack:
            v = stack.pop()
            for c in edge[v]:
                if group[c] == -1:
                    group[c] = cnt
                    stack.append(c)
        cnt += 1
for _ in range(int(input())):
    s, t = map(int, input().split())
    print('yes' if group[s] == group[t] else 'no')

Submission status: Accepted

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

import array
import collections


UNDEF = -1


def compute_connected_components(max_v, adj_list):
    group = array.array("l", (UNDEF for _ in range(max_v)))
    g_idx = 0
    for u in range(max_v):
        if group[u] == UNDEF:
            group[u] = g_idx
            q = collections.deque()
            q.append(u)
            while q:
                v = q.popleft()
                for w in adj_list[v]:
                    if group[w] == UNDEF:
                        group[w] = g_idx
                        q.append(w)
            else:
                g_idx += 1
    return group


def main():
    n, m = map(int, input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        s, t = map(int, input().split())
        adj_list[s].add(t)
        adj_list[t].add(s)
    group = compute_connected_components(n, adj_list)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print("yes" if group[s] == group[t] else "no")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from queue import deque

n, m = map(int, input().split())
G = deque([[] for i in range(n)]) #??°??????
for i in range(m):
    s, t = map(int, input().split())
    # ???????????£?????????????????????1????????\??????0
    G[s].append(t)
    G[t].append(s)


def dfs(r, c):
    S = deque()
    S.append(r)
    color[r] = c
    while (len(S) > 0):
        u = S.popleft()
        for j in G[u]:
            if color[j] == -1:
                # ???????????£???????????????????????¢?´¢????????????(???????????¢?´¢?????????????????????)
                color[j] = c
                S.append(j) # ?????????????????????????????¢???

def assginColor():
    i_d = 1
    for u in range(n):
        if color[u] == -1: #?????¢?´¢
            dfs(u, i_d)
            i_d += 1

color = [-1] * n
assginColor()
q = int(input())
s_t = [list(map(int, input().split())) for i in range(q)]
for s, t in s_t:
    if color[s] == color[t]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def bfs(i, c):
    global V, C

    q = []
    j = i
    while True:
        if C[j] == -1:
            C[j] = c
            q += V[j]
        if len(q) == 0:
            break
        j = q.pop()

n, m = map(int, raw_input().split())
V = [[] for _ in range(n)]
C = [-1] * n
for _ in range(m):
    l, r = map(int, raw_input().split())
    V[l].append(r)
    V[r].append(l)

c = 0
for i in range(n):
    if C[i] == -1:
        bfs(i, c)
        c += 1

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    if C[s] == C[t]:
        print "yes"
    else:
        print "no"

Submission status: Accepted

Solution code:
def bfs(i, c):
    global V, C

    q = [i]
    while len(q) > 0:
        j = q.pop()
        if C[j] == -1:
            C[j] = c
            q += V[j]

n, m = map(int, raw_input().split())
V = [[] for _ in range(n)]
C = [-1] * n
for _ in range(m):
    l, r = map(int, raw_input().split())
    V[l].append(r)
    V[r].append(l)

c = 0
for i in range(n):
    if C[i] == -1:
        bfs(i, c)
        c += 1

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    if C[s] == C[t]:
        print "yes"
    else:
        print "no"

Submission status: Accepted

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

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n


def dfs(u, group):
    path = []
    path.append(u)
    isVisited[u] = True
    CC[u] = group
    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not isVisited[v]:
                isVisited[v] = True
                CC[v] = group
                path.append(v)
        else:
            path.pop()

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Accepted

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

adj = [[] for i in range(n)]

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

groups = [None] * n


def dfs(u, group_num):
    path = []
    path.append(u)
    groups[u] = group_num
    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not groups[v]:
                groups[v] = group_num
                path.append(v)
        else:
            path.pop()


g_n = 1
for i in range(n):
    if not groups[i]:
        dfs(i, g_n)
        g_n += 1

def isConnected(v1, v2):
    if groups[v1] == groups[v2]:
        print('yes')
    else:
        print('no')


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Accepted

Solution code:
import sys
 
def make_connected_group(G):
    C = [None]*len(G)
    group = 0
    for i,p in enumerate(C):
        if p != None: continue
        friends = [i]
        while len(friends) > 0:
            f = friends.pop()
            if C[f] == None:
                C[f] = group
                friends += G[f]
        group += 1
    return C
 
 
if __name__=='__main__':
    n,m = list(map(int,sys.stdin.readline().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        s,t = list(map(int,input().split()))
        G[s].append(t)
        G[t].append(s)
    C = make_connected_group(G)
    q = int(input())
    for j,line in enumerate(sys.stdin):
        if not j < q: break
        s,t = list(map(int,line.split()))
        print('yes' if C[s] == C[t] else 'no')

Submission status: Accepted

Solution code:
import sys
 
def make_connected_group(G):
    C = [None]*len(G)
    group = 0
    for i,p in enumerate(C):
        if p != None: continue
        friends = [i]
        while len(friends) > 0:
            f = friends.pop()
            if C[f] == None:
                C[f] = group
                friends += G[f]
        group += 1
    return C
 
 
if __name__=='__main__':
    n,m = list(map(int,sys.stdin.readline().split()))
    G = [[] for _ in range(n)]
    for j,line in enumerate(sys.stdin):
        if not j < m:
            q = int(line)
            break
        s,t = list(map(int,line.split()))
        G[s].append(t)
        G[t].append(s)
    C = make_connected_group(G)
    for j,line in enumerate(sys.stdin):
        if not j < q: break
        s,t = list(map(int,line.split()))
        print('yes' if C[s] == C[t] else 'no')

Submission status: Accepted

Solution code:
def dfs(u, color):
    global c
    global g
    s = [u]
    c[u] = color
    while 0 < len(s):
        ch = s.pop()
        for ch in g[ch]:
            u_c = c[ch]
            if u_c is None:
                c[ch] = color
                s.append(ch)

def colorize():
    global g
    global c
    global n
    color = 1
    for i in range(n):
        if c[i] == None:
            dfs(i, color)
            color += 1

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

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

c = [None for i in range(n)]

colorize()

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

Submission status: Accepted

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

import sys


def assign_color():
    _id = 1
    for m in range(vertices_num):
        if vertices_status_list[m] == -1:
            graph_dfs(m, _id)
            _id += 1
    return None


def graph_dfs(vertex, color):
    vertices_stack = list()
    vertices_stack.append(vertex)
    vertices_status_list[vertex] = color
    while vertices_stack:
        current_vertex = vertices_stack[-1]
        vertices_stack.pop()
        for v in adj_list[current_vertex]:
            if vertices_status_list[v] == -1:
                vertices_status_list[v] = color
                vertices_stack.append(v)
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num, relation_num = map(int, _input[0].split())

    relation_info = _input[1:relation_num + 1]

    question_num = int(_input[relation_num + 1])
    question_list = _input[relation_num + 2:]

    adj_list = [[] for _ in range(vertices_num)]
    vertices_status_list = [-1] * vertices_num

    for relation in relation_info:
        key, value = map(int, relation.split())
        adj_list[key].append(value)
        adj_list[value].append(key)

    assign_color()

    # print(adj_list)
    for question in question_list:
        start, target = map(int, question.split())
        if vertices_status_list[start] == vertices_status_list[target]:
            print("yes")
        else:
            print("no")