#include "graph_tree/lex_bfs.hpp"
vector<int> lex_bfs(graph g,int n,int m){ list<list<int>>que; vector<list<list<int>>::iterator>pos1(n); vector<list<int>::iterator>pos2(n); list<int>s; rep(i,n)s.emplace_back(i); que.emplace_back(s); rep(i,n)pos1[i]=que.begin(); { int idx=0; for(auto i=que.front().begin();i!=que.front().end();++i){ pos2[idx++]=i; } } vector<int>used(n); vector<int>ans; while(!que.empty()){ auto v=que.front().front(); que.front().pop_front(); if(que.front().empty())que.pop_front(); ans.push_back(v); used[v]=1; for(auto e:g[v]){ if(used[e])continue; if(pos1[e]==que.begin()||prev(pos1[e])->front()!=-1){ que.insert(pos1[e],list<int>{-1}); } prev(pos1[e])->push_back(e); auto tmp1=prev(pos1[e]); auto tmp2=prev(tmp1->end()); pos1[e]->erase(pos2[e]); if(pos1[e]->empty())que.erase(pos1[e]); pos1[e]=tmp1; pos2[e]=tmp2; } for(auto e:g[v]){ if(used[e])continue; if(pos1[e]->front()==-1){ pos1[e]->pop_front(); } } } return ans; }
#line 1 "graph_tree/lex_bfs.hpp" vector<int> lex_bfs(graph g,int n,int m){ list<list<int>>que; vector<list<list<int>>::iterator>pos1(n); vector<list<int>::iterator>pos2(n); list<int>s; rep(i,n)s.emplace_back(i); que.emplace_back(s); rep(i,n)pos1[i]=que.begin(); { int idx=0; for(auto i=que.front().begin();i!=que.front().end();++i){ pos2[idx++]=i; } } vector<int>used(n); vector<int>ans; while(!que.empty()){ auto v=que.front().front(); que.front().pop_front(); if(que.front().empty())que.pop_front(); ans.push_back(v); used[v]=1; for(auto e:g[v]){ if(used[e])continue; if(pos1[e]==que.begin()||prev(pos1[e])->front()!=-1){ que.insert(pos1[e],list<int>{-1}); } prev(pos1[e])->push_back(e); auto tmp1=prev(pos1[e]); auto tmp2=prev(tmp1->end()); pos1[e]->erase(pos2[e]); if(pos1[e]->empty())que.erase(pos1[e]); pos1[e]=tmp1; pos2[e]=tmp2; } for(auto e:g[v]){ if(used[e])continue; if(pos1[e]->front()==-1){ pos1[e]->pop_front(); } } } return ans; }