blob: 6dc27bc466f5fc665db79809d320f0010377ef00 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
require 'set'
class SocialGraph
attr_reader :reader, :writer
def initialize(reader, writer)
@reader, @writer = reader, writer
@members = Hash.new { |hash, key| hash[key] = Member.new(key) }
end
def run(traversal = Traversal.new(writer))
(reader.readline.to_i - 1).times do
add_to_graph(reader.readline.strip)
end
member_for(reader.readline).tap do |root|
traversal.traverse(root)
end
end
private
def add_to_graph(line)
key, friend_keys = line.split(':')
friend_keys.split(',').each do |friend|
member_for(key).add_friend(member_for(friend))
end unless friend_keys.nil?
end
def member_for(key)
@members[key.strip]
end
end
class Member
include Enumerable
attr_reader :name
def initialize(name)
@name = name
@friends = []
end
def add_friend(friend)
@friends << friend
end
def each
@friends.each do |friend|
yield friend
end
end
def to_s
name
end
def inspect
name
end
def ==(other)
name == other.name
end
end
class Traversal
attr_reader :writer
def initialize(writer)
@writer = writer
@visited = { }
@queue = []
end
def traverse(member)
@queue = []
@root = member
@queue.push(member)
until @queue.empty? do
member = @queue.shift
write(newline) if member.nil? && @queue.first
next if member.nil?
visit(member)
added = false
member.each do |friend|
@queue.push(friend) if eligible?(friend)
added = true
end
@queue.push(nil) if added
end
end
private
def eligible?(member)
!visited?(member) && !root?(member) && !queued?(member)
end
def newline
"\n"
end
def queued?(friend)
@queue.find { |x| x == friend }
end
def visit(member)
return if visited?(member) || root?(member)
write(member.name) unless root?(member)
write(",") unless @queue.first.nil?
@visited[member.name] = true
end
def visited?(member)
@visited.key?(member.name)
end
def root?(member)
@root.name == member.name
end
def write(value)
writer.write(value)
end
end
|
