I’m reading the graphs solution to Livestock Lineup.

I don’t understand why sorting the adjacency lists and binary searching doesn’t achieve the same purpose as linearly finding the element.

```
#include <bits/stdc++.h>
using namespace std;
void setIO(string s=""){
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(15);
if(s.size()){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
#define F0R(i, n) for(int i=0; i<n; i++)
#define all(x) begin(x), end(x)
#define lb lower_bound
vector<string> cows{"Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"};
int index(string cow){ return lb(all(cows), cow) - begin(cows); }
vector<int> adj[8];
int main() {
setIO("lineup");
int N; cin >> N;
sort(all(cows));
F0R(i,N) {
string cow1, cow2, trash;
cin >> cow1 >> trash >> trash >> trash >> trash >> cow2;
int c1 = index(cow1), c2 = index(cow2); /// convert names to indices
adj[c1].push_back(c2), adj[c2].push_back(c1);
}
F0R(i,N) sort(all(adj[i]));
vector<int> seq; /// sequence of cow indices
vector<bool> done(8);
F0R(i,8) if (!done[i] && adj[i].size() <= 1) { /// add path to sequence
int cur = i;
while (adj[cur].size() == 1) {
seq.push_back(cur); done[cur] = 1;
int next = adj[cur].front();
adj[next].erase(lb(all(adj[next]), cur));
// adj[next].erase(find(all(adj[next]), cur));
cur = next;
}
seq.push_back(cur); done[cur] = 1;
}
for(int t: seq) cout << cows[t] << "\n"; /// convert indices back to names
}
```

Submitting this gives me a runtime error or memory limit exceed error on test cases 5, 6, and 8. Using `find()`

(commented out) in place of `lower_bound()`

gives AC.

Also, is it correct to say that we only visit each node’s adjacency list at most once in the line

`adj[next].erase(find(all(adj[next]), cur));`

?

Since we always mark done the nodes with an unvisited neighbor, it seems we only find and delete `cur`

from `adj[next]`

once. Then is it true that we visit the 2N total neighbors at most once with this `find`

command, so the solution runs in O(N)?

Part of my confusion is that we might visit `adj[next]`

for more nodes than just `cur`

. Or, we might visit `adj[next]`

more than once (worst case O(N^2)). Why are neither of these claims true?

Thanks in advance for helping me understand the internal solution.