Problem:

C: な◯りカット (Namo.. Cut)

問題

－謎の巨大クラゲ、 コードネーム「な◯り」を討伐せよ－

「な◯り」は非常に生命力が強いため、素早く切断し続けなければ、あっという間に復活してしまう。
我々は、「な◯り」をどのように切断するのが効率良いのか、日々試行錯誤している。
その過程で、あなた方プログラマの手が必要になった。

「な◯り」は N 頂点と N 辺からなる連結な無向グラフで表現できる。
以降、各頂点が 1 から N の異なる数で名前付けられているとしよう。

我々は、「な◯り」に関して Q 回の質問を行う。
それらすべてに答えるプログラムを作成して欲しい。

質問は 1 から Q の番号を持ち、各質問は次のように構成される。

 質問 i では 2 つの頂点 a_i と b_i が指定される。 a_i と b_i を非連結にするために、削除する必要のある辺の最小本数を答えよ。

ここで、頂点 u と v が非連結であるとは、 u と v を行き来できる経路が存在しないことを指す。

入力形式

N
u_1 v_1
u_2 v_2
...
u_N v_N
Q
a_1 b_1
a_2 b_2
...
a_Q b_Q

入力はすべて整数である。

1 行目には頂点数 N が与えられる。 
続く N 行のうち i 行目には、i 番目の辺が繋ぐ 2 頂点の番号 u_i, v_i が空白区切りで与えられる。

次に、質問の回数 Q が与えられる。
続く Q 行のうち i 行目には、i 番目の質問で指定される 2 頂点の番号 a_i, b_i が空白区切りで与えられる。

制約

 3 \leq N \leq 100,000

 1 \leq Q \leq 100,000

 グラフに自己ループ及び多重辺は存在しない

 1 \leq a_i, b_i \leq N かつ a_i \neq b_i (1 \leq i \leq Q)

出力形式

出力は Q 行からなる。
i 行目には、a_i と b_i を非連結にするために、削除する必要のある辺の最小本数を表す整数を出力せよ。

入力例1

3
1 2
1 3
2 3
1
1 3

出力例1

2

入力例2

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

出力例2

2
1
1



Sample input:
3
1 2
1 3
2 3
1
1 3


Sample output:
2

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/C

import collections

n = int(input().rstrip())

g = [[] for i in range(n)]
deg = [0 for i in range(n)]


for i in range(n):
    u, v = map(lambda x: x-1, map(int, input().rstrip().split(' ')))
    g[u].append(v)
    g[v].append(u)
    deg[u] += 1
    deg[v] += 1

q = collections.deque()

for i in range(n):
    if deg[i] == 1:
        q.append(i)

isPushed = [False for i in range(n)]

while len(q) > 0:
    v = q.popleft()
    isPushed[v] = True
    for nv in g[v]:
        deg[nv] -= 1

        if deg[nv] == 1:
            q.append(nv)

q = int(input().rstrip())

for _ in range(q):
    a, b = map(lambda x: x-1, map(int, input().rstrip().split(' ')))
    if isPushed[a] or isPushed[b]:
        print(1)
    else:
        print(2)

Submission status: Accepted

Solution code:
# サイクル検出
import sys
sys.setrecursionlimit(10**7) 

def dfs(G, v, p):
    global pos
    seen[v] = True
    hist.append(v)
    for nv in G[v]:
        # 逆流を禁止する
        if nv == p:
            continue

        # 完全終了した頂点はスルー
        if finished[nv]:
            continue

        # サイクルを検出
        if seen[nv] and not finished[nv]:
            pos = nv
            return
        
        # 再帰的に探索
        dfs(G, nv, v)

        # サイクル検出したならば真っ直ぐに抜けていく
        if pos != -1:
            return 
    hist.pop()
    finished[v] = True

# 頂点数 (サイクルを一つ含むグラフなので辺数は N で確定)
N = int(input())

# グラフ入力受取
G = [[] for _ in range(N)]
for i in range(N):
    a,b = map(int, input().split())
    # 頂点番号が 1-indexed で与えられるので 0-indexed にする
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

# 探索
seen = [False]*N
finished = [False]*N
pos = -1
hist = []
dfs(G, 0, -1)

# サイクルを復元
cycle = set()
while len(hist):
    t = hist.pop()
    cycle.add(t)
    if t == pos:
        break

# クエリに答える
Q = int(input())
for _ in range(Q):
    a,b = map(int, input().split())
    a-=1
    b-=1
    if a in cycle and b in cycle:
        print(2)
    else:
        print(1)

Submission status: Accepted

Solution code:
#=============================================================================
# サイクル検出 AOJ2891の解答例
#=============================================================================
import queue

N=int(input())
Graph=[[] for _ in range(N)]
deg=[0 for _ in range(N)]
que=queue.Queue()
circle=[True for _ in range(N)]

for _ in range(N):
    a,b=map(int,input().split())
    a-=1
    b-=1
    Graph[a].append(b)
    Graph[b].append(a)
    deg[a]+=1
    deg[b]+=1

for v in range(N):
    if deg[v]==1:
        que.put(v)
        circle[v]=False

while not que.empty():
    v=que.get()
    for nv in Graph[v]:
        deg[nv]-=1
        if deg[nv]==1:
            que.put(nv)
            circle[nv]=False

Q=int(input())
for _ in range(Q):
    a,b=map(int,input().split())
    if circle[a-1] and circle[b-1]:
        print(2)
    else:
        print(1)

Submission status: Accepted

Solution code:
import copy ; import sys ;input = sys.stdin.readline; sys.setrecursionlimit(11451419);from collections  import deque 
n=int(input())
G=[[] for i in range(n)]
for i in range(n):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
seen=[0 for i in range(n)]

hist=deque([]) #頂点の訪問履歴
pos=-1  #サイクルの1成分 -1はサイクル未発見

def dfs(x,p):  #pはxの親
    global pos #global!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    seen[x]=1
    hist.append(x)  #訪れたらhistにappend
    for to in G[x]:
        if to==p:continue  #親なら無視
        if seen[to]==1:
            pos=to
            return    #サイクルを発見したら、即すべてのdfsを終える
        #残りはseen[x]=0のみ
        dfs(to,x)
        if pos != -1:return  #帰りがけ、サイクルが検出済みなら何もしない
    hist.pop()  #stackの末尾を消す
    #ループなく平和に終わったらpopできる
    return  #まあなくてもいいけどreturnは終了であることを強調

dfs(0,-1)

#この状態だと、サイクルに入る前に通った枝葉がhistに入ってる。
#枝葉が終わったら、posからループの順番に頂点番号が入ってる。
cycle=set([])
while hist:
    qwe=hist.pop()
    cycle.add(qwe)
    if qwe==pos:break
    #そっかこっちの方が速いよね～～～～～indexだとちょっとアレだよね～～～～～～～～～～～～～～～～～～～～～～はい
    
m=int(input())
for i in range(m):
    a,b=map(int,input().split())
    if a-1 in cycle  and  b-1 in cycle:
        print(2)
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

def dfs(v, p):
    global pos
    
    seen[v] = True
    hist.append(v)

    for nv in adj_list[v]:
        if nv==p:
            continue
        
        if seen[nv]:
            pos = nv
            return
        
        dfs(nv, v)
        
        if pos!=-1:
            return
    
    hist.pop()

N = int(input())
adj_list = [[] for _ in range(N)]

for _ in range(N):
    ui, vi = map(int, input().split())
    adj_list[ui-1].append(vi-1)
    adj_list[vi-1].append(ui-1)

seen = [False]*N
hist = deque([])
pos = -1
dfs(0, -1)
cycle = set()

while hist:
    t = hist.pop()
    cycle.add(t)
    
    if t==pos:
        break

Q = int(input())

for _ in range(Q):
    ai, bi = map(int, input().split())
    
    if ai-1 in cycle and bi-1 in cycle:
        print(2)
    else:
        print(1)