Submission #25521687

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N,M,S = gets.split.map(&:to_i)
E = Array.new(N+1){[]}
M.times{
  uv = gets.split.map(&:to_i)
  E[uv.min]<<uv
}
G = [-1]*(N+1)
F = lambda{|u|
  G[u]<0 ? u : G[u] = F[G[u]]
}
U = lambda{|uv|
  u,v = uv.map(&F)
  next if u==v
  u,v = v,u if G[v]<G[u]
  G[u] += G[v]
  G[v] = u
}
E[S+1..N].flatten(1).each(&U)
puts S.downto(1).select{|u|
  E[u].each(&U)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N,M,S = gets.split.map(&:to_i)
E = Array.new(N+1){[]}
M.times{
	uv = gets.split.map(&:to_i)
	E[uv.min]<<uv
}

G = [-1]*(N+1)
F = lambda{|u|
	G[u]<0 ? u : G[u] = F[G[u]]
}
U = lambda{|uv|
	u,v = uv.map(&F)
	next if u==v
	u,v = v,u if G[v]<G[u]
	G[u] += G[v]
	G[v] = u
}
E[S+1..N].flatten(1).each(&U)
puts S.downto(1).select{|u|
	E[u].each(&U)
	next F[u]==F[S]
}.reverse

Submission Info

Judge Result