Skip to content

Instantly share code, notes, and snippets.

@NachiaVivias
Created September 28, 2022 12:22
Show Gist options
  • Save NachiaVivias/863a1b75666920101a52165baaada48d to your computer and use it in GitHub Desktop.
Save NachiaVivias/863a1b75666920101a52165baaada48d to your computer and use it in GitHub Desktop.
trash
#line 1 "Main.cpp"
#line 2 "nachia\\misc\\sorting.hpp"
#include <vector>
#include <cassert>
#include <algorithm>
namespace nachia{
template<class Iterator>
void EnsurePermutation(Iterator first, Iterator last){
int n = std::distance(first, last);
std::vector<int> vis(n, 0);
for(Iterator i=first; i!=last; i++){
assert(0 <= *i);
assert(*i < n);
assert(vis[*i] == 0);
vis[*i] = 1;
}
}
template<class T> std::vector<T> Permute(
const std::vector<T>& src,
const std::vector<int>& perm
){
const bool DEBUG = true;
int n = src.size();
if constexpr (DEBUG){
assert(perm.size() == src.size());
EnsurePermutation(perm.begin(), perm.end());
}
std::vector<T> res;
res.reserve(n);
for(int i=0; i<n; i++) res.push_back(src[perm[i]]);
return res;
}
template<class T> std::vector<T>& PermuteInPlace(
std::vector<T>& src,
std::vector<int> perm
){
const bool DEBUG = true;
int n = src.size();
if constexpr (DEBUG){
assert(perm.size() == src.size());
EnsurePermutation(perm.begin(), perm.end());
}
for(int s=0; s<n; s++){
int p = s;
while(perm[p] != s){
std::swap(src[p], src[perm[p]]);
std::swap(p, perm[p]);
}
perm[p] = p;
}
return src;
}
// stable sort
std::vector<int> BucketSortPermutation(
std::vector<int>::const_iterator first,
std::vector<int>::const_iterator last,
int maxVal
){
const bool DEBUG = true;
int n = last - first;
if constexpr (DEBUG){
for(auto itr = first; itr != last; itr++){
assert(0 <= *itr);
assert(*itr <= maxVal);
}
}
std::vector<int> cnt(maxVal+2);
std::vector<int> res(n);
for(int i=0; i<n; i++) cnt[first[i]+1]++;
for(int i=0; i<maxVal; i++) cnt[i+1] += cnt[i];
for(int i=0; i<n; i++) res[cnt[first[i]]++] = i;
return res;
}
// stable sort
template<class T, class Mapping>
std::vector<int> BucketSortPermutation(
typename std::vector<T>::const_iterator first,
typename std::vector<T>::const_iterator last,
const Mapping& f,
int maxVal
){
std::vector<int> buf(last - first);
auto bufitr = buf.begin();
for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr);
return BucketSortPermutation(buf.begin(), buf.end(), maxVal);
}
// stable sort
template<class T, class Mapping>
std::vector<T> BucketSort(
std::vector<T> src,
const Mapping& f,
int maxVal
){
return PermuteInPlace(src, BucketSortPermutation<T>(src.begin(), src.end(), f, maxVal));
}
}
#line 2 "nachia\\graph\\double-low.hpp"
#line 2 "nachia\\array\\csr-array.hpp"
#include <utility>
#line 5 "nachia\\array\\csr-array.hpp"
namespace nachia{
template<class Elem>
class CsrArray{
public:
struct ListRange{
using iterator = typename std::vector<Elem>::iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
Elem& operator[](int i) const { return begi[i]; }
};
struct ConstListRange{
using iterator = typename std::vector<Elem>::const_iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
const Elem& operator[](int i) const { return begi[i]; }
};
private:
int m_n;
std::vector<Elem> m_list;
std::vector<int> m_pos;
public:
CsrArray() : m_n(0), m_list(), m_pos() {}
static CsrArray Construct(int n, const std::vector<std::pair<int, Elem>>& items){
CsrArray res;
res.m_n = n;
std::vector<int> buf(n+1, 0);
for(auto& [u,v] : items){ ++buf[u]; }
for(int i=1; i<=n; i++) buf[i] += buf[i-1];
res.m_list.resize(buf[n]);
for(int i=(int)items.size()-1; i>=0; i--){
res.m_list[--buf[items[i].first]] = items[i].second;
}
res.m_pos = std::move(buf);
return res;
}
static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
CsrArray res;
res.m_n = pos.size() - 1;
res.m_list = std::move(list);
res.m_pos = std::move(pos);
return res;
}
ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
int size() const { return m_n; }
int fullSize() const { return (int)m_list.size(); }
};
} // namespace nachia
#line 3 "nachia\\graph\\dfs-tree.hpp"
namespace nachia{
struct DfsTree{
std::vector<int> dfsOrd;
std::vector<int> parent;
static DfsTree Construct(int n, const std::vector<std::pair<int, int>>& edges, bool OutOrd){
DfsTree res;
auto adj = CsrArray<int>::Construct(n, edges);
res.dfsOrd.reserve(n);
std::vector<int> eid(n, 0);
std::vector<int> parent(n, -2);
for(int s=0; s<n; s++) if(parent[s] == -2){
int p = s;
if(p >= n) p -= n;
parent[p] = -1;
while(0 <= p){
if(eid[p] == (OutOrd ? (int)adj[p].size() : 0)) res.dfsOrd.push_back(p);
if(eid[p] == (int)adj[p].size()){ p = parent[p]; continue; }
int nx = adj[p][eid[p]++];
if(parent[nx] != -2) continue;
parent[nx] = p;
p = nx;
}
}
res.parent = std::move(parent);
return res;
}
};
} // namespace nachia
#line 5 "nachia\\graph\\double-low.hpp"
namespace nachia{
struct DoubleLowAndOrdering{
std::vector<int> inOrder;
std::vector<int> inIndex;
std::vector<int> parent;
std::vector<int> lowpt1;
std::vector<int> lowpt2;
std::vector<int> nd;
std::vector<int> edgeOrd;
CsrArray<int> adj;
// input : simple undirected graph
void calc(){
int n = adj.size();
{
inOrder = {0};
parent.assign(n, -1); parent[0] = -2;
std::vector<int> EI(n, 0);
int p = 0;
while(p >= 0){
if(EI[p] == adj[p].size()){ p = parent[p]; continue; }
int q = adj[p][EI[p]++];
if(parent[q] != -1) continue;
parent[q] = p; p = q;
inOrder.push_back(p);
}
inIndex.resize(n);
for(int i=0; i<n; i++) inIndex[inOrder[i]] = i;
lowpt1.resize(n);
for(int i=0; i<n; i++) lowpt1[i] = inIndex[i];
lowpt2.resize(n);
for(int i=0; i<n; i++) lowpt2[i] = inIndex[i];
}
auto insertLow = [&](int p, int low){
if(lowpt1[p] == low) return;
if(lowpt1[p] > low) std::swap(lowpt1[p], low);
if(lowpt2[p] == low) return;
if(lowpt2[p] > low) std::swap(lowpt2[p], low);
};
nd.assign(n, 1);
for(int vi=n-1; vi>=0; vi--){
int v = inOrder[vi];
for(auto& e : adj[v]) if(parent[v] != e && inIndex[e] < inIndex[v]){
if(parent[e] != v) insertLow(v, inIndex[e]);
}
if(parent[v] < 0) continue;
insertLow(parent[v], lowpt1[v]);
insertLow(parent[v], lowpt2[v]);
nd[parent[v]] += nd[v];
}
}
// input : simple undirected graph
DoubleLowAndOrdering(int n, std::vector<std::pair<int, int>> edges){
{
std::vector<std::pair<int, int>> xedges;
for(auto& e : edges) xedges.push_back({ e.first, e.second });
for(auto& e : edges) xedges.push_back({ e.second, e.first });
adj = CsrArray<int>::Construct(n, std::move(xedges));
calc();
}
for(auto& e : edges){
int& v = e.first; int& w = e.second;
if(parent[v] == w) std::swap(v, w);
if(parent[w] != v) if(inIndex[v] < inIndex[w]) std::swap(v, w);
}
auto edgePriority =
[&](const std::pair<int, int>& tg) -> int {
int v = tg.first, w = tg.second;
if(v != parent[w]) return 3 * inIndex[w]+1;
return 3 * lowpt1[w] + ((lowpt2[w] < inIndex[v]) ? 0 : 2);
};
edgeOrd = BucketSortPermutation<std::pair<int, int>>(edges.begin(), edges.end(), edgePriority, 3*n-1);
PermuteInPlace(edges, edgeOrd);
std::reverse(edges.begin(), edges.end());
adj = CsrArray<int>::Construct(n, std::move(edges));
calc();
}
};
} // namespace nachia
#line 4 "Main.cpp"
#include <iostream>
#line 8 "Main.cpp"
#include <chrono>
struct SPQRTree{
struct Component;
struct Edge;
// {a,b} is a potential type-2 separation pair,
// and h is the highest numbered vertex in the component that would be split off
struct HABTriplet{
int h, a, b;
bool isEOS() const { return h == -1; }
static HABTriplet getEOS() { return {-1,-1,-1}; }
};
struct SPQRNode{};
struct Edge{
int from;
int to;
bool start;
bool isTreeEdge;
bool isVirtual;
bool inGc;
int component1;
int component2;
};
struct Vertex{
int parent;
int treeArc;
int degree;
int lowpt1;
int lowpt2;
int nd;
int unvisitedTreeArcCount = 0;
};
enum class ComponentType{ Unknown, S, P, R };
static std::string ComponentTypeString(ComponentType t){
switch(t){
case ComponentType::Unknown: return "Unknown";
case ComponentType::S: return "S";
case ComponentType::P: return "P";
case ComponentType::R: return "R";
}
return "Undefined";
}
struct Component{
std::vector<int> edges;
ComponentType ty = ComponentType::Unknown;
};
std::vector<Vertex> vtx;
std::vector<Edge> edges;
std::vector<int> AdjNx;
std::vector<int> AdjHead;
std::vector<int> FrondNx, FrondHead, FrondTail;
std::vector<int> Estack;
std::vector<HABTriplet> Tstack;
int Eitr, Titr;
std::vector<Component> components;
void RemoveEdgeFromGc(int ei){
auto& e = edges[ei];
vtx[e.from].degree--;
vtx[e.to].degree--;
if(e.from > e.to) std::swap(e.from, e.to);
e.inGc = false;
}
void AddEdgeToComponent(int c, int ei){
components[c].edges.push_back(ei);
edges[ei].component1 = c;
RemoveEdgeFromGc(ei);
}
int NewComponent(std::vector<int> E){
auto c = components.size();
components.push_back(Component{});
for(auto ei : E){
RemoveEdgeFromGc(ei);
edges[ei].component1 = c;
}
components[c].edges = std::move(E);
return c;
}
void PushFrond(int v, int e){
if(FrondTail[v] >= 0) FrondNx[FrondTail[v]] = e;
FrondTail[v] = e;
if(FrondHead[v] < 0) FrondHead[v] = e;
}
bool IsAnEdgeOf(int ei, int v, int w){
auto& e = edges[ei];
if(e.from == v && e.to == w) return true;
if(e.from == w && e.to == v) return true;
return false;
}
void InsertAdj(int ei, int v){ AdjNx[ei] = AdjHead[v]; AdjHead[v] = ei; }
int NewComponent2(std::vector<int> E, int v, int w, bool treeEdge){
auto c = components.size();
components.push_back(Component{});
int ei = E.back() = edges.size();
for(auto ei : E) if(ei != E.back()){
RemoveEdgeFromGc(ei);
edges[ei].component1 = c;
}
components[c].edges = std::move(E);
AdjNx.push_back(-1);
edges.emplace_back();
auto& e = edges[ei];
e.from = v;
e.to = w;
e.isTreeEdge = treeEdge;
e.isVirtual = true;
e.start = false;
e.inGc = true;
e.component1 = -1;
e.component2 = c;
vtx[v].degree++;
vtx[w].degree++;
if(treeEdge){
vtx[w].treeArc = ei;
vtx[w].parent = v;
InsertAdj(ei, v);
}
else PushFrond(w, ei);
return ei;
}
int FirstChild(int w){
int& adj = AdjHead[w];
while(adj >= 0 && !edges[adj].inGc) adj = AdjNx[adj];
return (adj < 0) ? -1 : edges[adj].to;
}
int Parent(int x){ return vtx[x].parent; }
int Deg(int x){ return vtx[x].degree; }
bool DoStartAPath(int ei){ return edges[ei].start; }
int High(int x){
for(int& e=FrondHead[x]; e>=0; e=FrondNx[e]) if(edges[e].inGc && !edges[e].isTreeEdge) return edges[e].from;
return -1;
}
bool IsAdjacentToANotYetVisitedTreeArc(int x){ return vtx[x].unvisitedTreeArcCount != 0; }
int Root(){ return 0; }
std::vector<int> adjBuf;
void PathSearch(int v){
auto t0 = std::chrono::high_resolution_clock::now();
bool ret = false;
while(v >= 0){
int ei = adjBuf[v];
int w = edges[ei].to;
if(ret){
Estack[++Eitr] = vtx[w].treeArc;
vtx[v].unvisitedTreeArcCount--;
// BEGIN : check for type-2 pairs
while(true){
int tmpa = Tstack[Titr].a;
// deg(w) == 2 のケースは Tstack.back() == EOF でも適用される
if(v != Root() && (tmpa == v || (Deg(w) == 2 && FirstChild(w) > w))); else break;
int h = Tstack[Titr].h, a = Tstack[Titr].a, b = Tstack[Titr].b;
if(a == v && Parent(b) == a){ Titr--; continue; }
int x = FirstChild(w);
int eab = -1;
int ep = -1;
if(Deg(w) == 2 && x > w){
// v -> w -> x : triangle を作れる
ep = NewComponent2({ Estack[Eitr], Estack[Eitr-1], -1 }, v, x, true);
Eitr -= 2;
if(IsAnEdgeOf(Estack[Eitr], v, x)) eab = Estack[Eitr--];
}
else{
Titr--;
int EitrR = Eitr;
while(Eitr >= 0){
int x = edges[Estack[Eitr]].from, y = edges[Estack[Eitr]].to;
if(a <= x && x <= h && a <= y && y <= h); else break;
if(IsAnEdgeOf(Estack[Eitr], a, b)){ eab = Estack[Eitr]; Estack[Eitr] = Estack[EitrR--]; }
Eitr--;
}
ep = NewComponent2(std::vector<int>(Estack.begin()+(Eitr+1), Estack.begin()+(EitrR+2)), a, b, true);
x = b;
}
if(eab != -1) ep = NewComponent2({ eab, ep, -1 }, v, b, true);
Estack[++Eitr] = ep;
w = x;
}
// END : check for type-2 pairs
// BEGIN : check for a type-1 pair
if(vtx[w].lowpt2 >= v && vtx[w].lowpt1 < v && (Parent(v) != Root() || IsAdjacentToANotYetVisitedTreeArc(v))){
int EitrR = Eitr;
while(Eitr >= 0){
int x = edges[Estack[Eitr]].from, y = edges[Estack[Eitr]].to;
if(!((w <= x && x < w+vtx[w].nd) || (w <= y && y < w+vtx[w].nd))) break;
Eitr--;
}
auto ep = NewComponent2(std::vector<int>(Estack.begin()+(Eitr+1), Estack.begin()+(EitrR+2)), v, vtx[w].lowpt1, false);
if(Eitr >= 0 && IsAnEdgeOf(Estack[Eitr], v, vtx[w].lowpt1)){
ep = NewComponent2({ Estack[Eitr--], ep, -1 }, v, vtx[w].lowpt1, false);
}
if(vtx[w].lowpt1 != Parent(v)) Estack[++Eitr] = ep;
else ep = NewComponent2({ ep, vtx[v].treeArc, -1 }, vtx[w].lowpt1, v, true);
}
// END : check for a type-1 pair
if(DoStartAPath(ei)) while(!(Tstack[Titr--].isEOS()));
int High_v = High(v);
while(!(Tstack[Titr].isEOS())){
auto hab = Tstack[Titr];
if(hab.a != v && hab.b != v && High_v > hab.h) Titr--; else break;
}
}
else{
if(edges[ei].isTreeEdge){
if(DoStartAPath(ei)){
int h = w + vtx[w].nd - 1, a = vtx[w].lowpt1, b = v;
while(!Tstack[Titr].isEOS() && Tstack[Titr].a > vtx[w].lowpt1){
h = std::max(h, Tstack[Titr].h);
b = Tstack[Titr].b;
Titr--;
}
Tstack[++Titr] = HABTriplet{ h, a, b };
Tstack[++Titr] = HABTriplet::getEOS();
}
v = w; ret = false; continue;
}
else{
PushFrond(w, ei); // visit a frond
if(DoStartAPath(ei)){
int h = -1, b = v;
while(!Tstack[Titr].isEOS() && Tstack[Titr].a > w){
h = std::max(h, Tstack[Titr].h);
b = Tstack[Titr].b;
Titr--;
}
Tstack[++Titr] = HABTriplet{ (h<0 ? v : h), w, b };
}
if(w == Parent(v)) NewComponent2({ ei, vtx[v].treeArc, -1 }, w, v, true);
else Estack[++Eitr] = ei;
}
}
adjBuf[v] = AdjNx[adjBuf[v]]; ret = false;
if(adjBuf[v] < 0){ v = Parent(v); ret = true; }
}
auto t1 = std::chrono::high_resolution_clock::now();
std::cerr << "time PathSearch = " << (t1-t0).count() << " ns\n";
}
void InitializeSimple(int N, std::vector<int> eitrs){
auto t0 = std::chrono::high_resolution_clock::now();
adjBuf.resize(N);
std::vector<int> edgeOrd, inOrder;
{
std::vector<std::pair<int, int>> tgedges;
for(auto a : eitrs){
tgedges.push_back({ edges[a].from, edges[a].to });
edges[a].inGc = true;
}
nachia::DoubleLowAndOrdering doubleLow(N, std::move(tgedges));
vtx.resize(N);
for(int i=0; i<N; i++){
int newid = doubleLow.inIndex[i];
vtx[newid].lowpt1 = doubleLow.lowpt1[i];
vtx[newid].lowpt2 = doubleLow.lowpt2[i];
vtx[newid].parent = (doubleLow.parent[i] < 0) ? -1 : doubleLow.inIndex[doubleLow.parent[i]];
vtx[newid].degree = 0;
vtx[newid].nd = doubleLow.nd[i];
}
edgeOrd = std::move(doubleLow.edgeOrd);
inOrder = std::move(doubleLow.inOrder);
for(auto& e : edges){
e.from = doubleLow.inIndex[e.from];
e.to = doubleLow.inIndex[e.to];
}
}
AdjHead.assign(N, -1);
AdjNx.assign(edges.size(), -1);
FrondNx.assign(edges.size()*2, -1);
FrondHead.assign(N, -1);
FrondTail.assign(N, -1);
std::reverse(edgeOrd.begin(), edgeOrd.end());
for(int i : edgeOrd){
int ei = eitrs[i];
auto& e = edges[ei];
int& v = e.from;
int& w = e.to;
vtx[v].degree++; vtx[w].degree++;
if(vtx[w].parent == v || vtx[v].parent == w) /* v --> w */ {
if(vtx[v].parent == w) std::swap(v, w);
e.isTreeEdge = true;
e.start = true;
InsertAdj(ei, v);
vtx[w].treeArc = ei;
vtx[v].unvisitedTreeArcCount++;
}
else /* v ~~> w */ {
if(v < w) std::swap(v, w);
e.isTreeEdge = false;
e.start = true;
InsertAdj(ei, v);
}
}
for(int v=1; v<N; v++) edges[AdjHead[v]].start = false;
adjBuf = AdjHead;
Titr = 0; Tstack.assign(eitrs.size()*2, HABTriplet::getEOS());
Eitr = -1; Estack.resize(eitrs.size()+1);
PathSearch(0);
if(Eitr) NewComponent(std::vector<int>(Estack.begin(), Estack.begin() + Eitr+1));
for(auto& e : edges){
e.from = inOrder[e.from];
e.to = inOrder[e.to];
}
auto t1 = std::chrono::high_resolution_clock::now();
std::cerr << "time InitializeSimple = " << (t1-t0).count() << " ns\n";
}
void FixEdges(){
std::vector<int> Map(edges.size(), -1);
int n = 0;
for(size_t i=0; i<edges.size(); i++) if(edges[i].from != -1){
Map[i] = n++;
std::swap(edges[Map[i]], edges[i]);
}
for(auto& c : components) for(auto& e : c.edges) e = Map[e];
edges.resize(n);
}
void FixComponents(){
std::vector<int> Map(components.size(), -1);
int n = 0;
for(size_t i=0; i<components.size(); i++) if(components[i].ty != ComponentType::Unknown){
Map[i] = n++;
std::swap(components[Map[i]], components[i]);
}
for(auto& e : edges){
e.component1 = Map[e.component1];
e.component2 = Map[e.component2];
}
components.resize(n);
}
void Initialize(int N, std::vector<std::pair<int, int>> edges){
auto t0 = std::chrono::high_resolution_clock::now();
int initEdgeNum = edges.size();
std::vector<int> st;
{
std::vector<int> I(initEdgeNum); // edge sort index
for(auto& e : edges) e = std::minmax((int)e.first, (int)e.second);
for(int i=0; i<(int)edges.size(); i++) I[i] = i;
I = nachia::BucketSort(I, [&](int i){ return edges[i].second; }, N-1);
I = nachia::BucketSort(I, [&](int i){ return edges[i].first; }, N-1);
auto NewEmptyEdge = [&](std::pair<int, int> vw, bool isVirtual) -> int {
Edge e;
e.from = vw.first;
e.to = vw.second;
e.isVirtual = isVirtual;
e.component1 = e.component2 = -1;
this->edges.push_back(e);
return this->edges.size() - 1;
};
auto NewPNode = [&](int a, int b) -> int {
int c = components.size();
components.push_back(Component());
int ep = NewEmptyEdge({ this->edges[a].from, this->edges[a].to }, true);
this->edges[a].component1 = c;
this->edges[b].component1 = c;
this->edges[ep].component2 = c;
components[c].edges = { a, b, ep };
components[c].ty = ComponentType::P;
return ep;
};
st.push_back(NewEmptyEdge(edges[I[0]], false));
for(int i=1; i<(int)I.size(); i++){
int e1 = NewEmptyEdge(edges[I[i]], false), e2 = st.back();
if(!st.empty() && this->edges[e1].from == this->edges[e2].from && this->edges[e1].to == this->edges[e2].to){
st.back() = NewPNode(e1, e2);
}
else{
st.push_back(e1);
}
}
}
InitializeSimple(N, st);
for(auto& c : components) if(c.ty == ComponentType::Unknown){
if(c.edges.size() != 3) c.ty = ComponentType::R;
else{
auto e1 = c.edges.begin();
auto e2 = c.edges.begin(); e2++;
if(IsAnEdgeOf(*e1, this->edges[*e2].from, this->edges[*e2].to)) c.ty = ComponentType::P;
else c.ty = ComponentType::S;
}
}
for(int ci=0; ci<(int)components.size(); ci++){
auto& c = components[ci];
if(c.ty != ComponentType::P && c.ty != ComponentType::S) continue;
for(size_t i=0; i<c.edges.size(); i++){
auto ei = c.edges[i];
auto& e = this->edges[ei];
if(!(e.isVirtual)) continue;
auto ci2 = (e.component1 == ci) ? e.component2 : e.component1;
auto& c2 = components[ci2];
if(c2.ty != c.ty) continue;
for(int e2i : c2.edges){
if(e2i == ei) continue;
c.edges.push_back(e2i);
if(this->edges[e2i].component1 == ci2) this->edges[e2i].component1 = ci; else this->edges[e2i].component2 = ci;
}
c2.edges.clear();
e.from = -1;
std::swap(c.edges.back(), c.edges[i]); c.edges.pop_back(); i--;
c2.ty = ComponentType::Unknown;
}
}
FixEdges();
FixComponents();
auto t1 = std::chrono::high_resolution_clock::now();
std::cerr << "time Initialize = " << (t1-t0).count() << " ns\n";
}
};
#line 2 "nachia\\misc\\fastio.hpp"
#include <cstdio>
#include <string>
namespace nachia{
const unsigned int INPUT_BUF_SIZE = 1 << 17;
const unsigned int OUTPUT_BUF_SIZE = 1 << 17;
char input_buf[INPUT_BUF_SIZE];
struct InputBufIterator{
private:
unsigned int p = INPUT_BUF_SIZE;
public:
using MyType = InputBufIterator;
static bool is_whitespace(char ch){
switch(ch){
case ' ': case '\n': case '\r': case '\t': return true;
}
return false;
}
char seek_char(){
if(p == INPUT_BUF_SIZE){
size_t len = fread(input_buf, 1, INPUT_BUF_SIZE, stdin);
if(len != INPUT_BUF_SIZE) input_buf[len] = '\0';
p = 0;
}
return input_buf[p];
}
void skip_whitespace(){
while(is_whitespace(seek_char())) p++;
}
unsigned int next_uint(){
skip_whitespace();
unsigned int buf = 0;
while(true){
char tmp = seek_char();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
int next_int(){
skip_whitespace();
if(seek_char() == '-'){
p++;
return (int)(-next_uint());
}
return (int)next_uint();
}
unsigned long long next_ulong(){
skip_whitespace();
unsigned long long buf = 0;
while(true){
char tmp = seek_char();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
long long next_long(){
skip_whitespace();
if(seek_char() == '-'){
p++;
return (long long)(-next_ulong());
}
return (long long)next_ulong();
}
char next_char(){
skip_whitespace();
char buf = seek_char();
p++;
return buf;
}
std::string next_token(){
skip_whitespace();
std::string buf;
while(true){
char ch = seek_char();
if(is_whitespace(ch) || ch == '\0') break;
buf.push_back(ch);
p++;
}
return buf;
}
MyType& operator>>(unsigned int& dest){ dest = next_uint(); return *this; }
MyType& operator>>(int& dest){ dest = next_int(); return *this; }
MyType& operator>>(unsigned long& dest){ dest = next_ulong(); return *this; }
MyType& operator>>(long& dest){ dest = next_long(); return *this; }
MyType& operator>>(unsigned long long& dest){ dest = next_ulong(); return *this; }
MyType& operator>>(long long& dest){ dest = next_long(); return *this; }
MyType& operator>>(std::string& dest){ dest = next_token(); return *this; }
MyType& operator>>(char& dest){ dest = next_char(); return *this; }
};
char output_buf[OUTPUT_BUF_SIZE] = {};
struct FastOutputTable{
char dig3lz[1000][4];
char dig3nlz[1000][4];
FastOutputTable(){
for(unsigned int d=0; d<1000; d++){
unsigned int x = d;
unsigned int i = 0;
dig3lz[d][i++] = ('0' + x / 100 % 10);
dig3lz[d][i++] = ('0' + x / 10 % 10);
dig3lz[d][i++] = ('0' + x / 1 % 10);
dig3lz[d][i++] = '\0';
}
for(unsigned int d=0; d<1000; d++){
unsigned int x = d;
unsigned int i = 0;
if(x >= 100) dig3nlz[d][i++] = ('0' + x / 100 % 10);
if(x >= 10) dig3nlz[d][i++] = ('0' + x / 10 % 10);
if(x >= 1) dig3nlz[d][i++] = ('0' + x / 1 % 10);
dig3nlz[d][i++] = '\0';
}
}
} fastoutput_table_inst;
struct OutputBufIterator{
using MyType = OutputBufIterator;
unsigned int p = 0;
static constexpr unsigned int POW10(int d){ return (d<=0) ? 1 : (POW10(d-1)*10); }
static constexpr unsigned long long POW10LL(int d){ return (d<=0) ? 1 : (POW10LL(d-1)*10); }
void next_char(char c){
output_buf[p++] = c;
if(p == OUTPUT_BUF_SIZE){
fwrite(output_buf, p, 1, stdout);
p = 0;
}
}
void next_eoln(){
next_char('\n');
}
void next_cstr(const char* s){
unsigned int i = 0;
while(s[i]) next_char(s[i++]);
}
void next_dig9(unsigned int x){
unsigned int y;
y = x / POW10(6); x -= y * POW10(6);
next_cstr(fastoutput_table_inst.dig3lz [y]);
y = x / POW10(3); x -= y * POW10(3);
next_cstr(fastoutput_table_inst.dig3lz [y]);
y = x;
next_cstr(fastoutput_table_inst.dig3lz [y]);
}
void next_uint(unsigned int x){
unsigned int y = 0;
if(x >= POW10(9)){
y = x / POW10(9); x -= y * POW10(9);
next_cstr(fastoutput_table_inst.dig3nlz[y]);
next_dig9(x);
}
else if(x >= POW10(6)){
y = x / POW10(6); x -= y * POW10(6);
next_cstr(fastoutput_table_inst.dig3nlz[y]);
y = x / POW10(3); x -= y * POW10(3);
next_cstr(fastoutput_table_inst.dig3lz [y]);
next_cstr(fastoutput_table_inst.dig3lz [x]);
}
else if(x >= POW10(3)){
y = x / POW10(3); x -= y * POW10(3);
next_cstr(fastoutput_table_inst.dig3nlz[y]);
next_cstr(fastoutput_table_inst.dig3lz [x]);
}
else if(x >= 1){
next_cstr(fastoutput_table_inst.dig3nlz[x]);
}
else{
next_char('0');
}
}
void next_int(int x){
if(x >= 0) next_uint(x);
else{
next_char('-');
next_uint((unsigned int)-x);
}
}
void next_ulong(unsigned long long x){
unsigned int y = 0;
if(x >= POW10LL(18)){
y = x / POW10LL(18); x -= y * POW10LL(18);
next_uint(y);
y = x / POW10LL(9); x -= y * POW10LL(9);
next_dig9(y);
next_dig9(x);
}
else if(x >= POW10LL(9)){
y = x / POW10LL(9); x -= y * POW10LL(9);
next_uint(y);
next_dig9(x);
}
else{
next_uint(x);
}
}
void next_long(long long x){
if(x >= 0) next_ulong(x);
else{
next_char('-');
next_ulong((unsigned long long)-x);
}
}
void write_to_file(bool flush = false){
fwrite(output_buf, p, 1, stdout);
if(flush) fflush(stdout);
p = 0;
}
~OutputBufIterator(){ write_to_file(); }
MyType& operator<<(unsigned int tg){ next_uint(tg); return *this; }
MyType& operator<<(unsigned long tg){ next_ulong(tg); return *this; }
MyType& operator<<(unsigned long long tg){ next_ulong(tg); return *this; }
MyType& operator<<(int tg){ next_int(tg); return *this; }
MyType& operator<<(long tg){ next_long(tg); return *this; }
MyType& operator<<(long long tg){ next_long(tg); return *this; }
MyType& operator<<(const std::string& tg){ next_cstr(tg.c_str()); return *this; }
MyType& operator<<(const char* tg){ next_cstr(tg); return *this; }
MyType& operator<<(char tg){ next_char(tg); return *this; }
};
} // namespace nachia
#line 443 "Main.cpp"
int main() {
nachia::InputBufIterator cin;
nachia::OutputBufIterator cout;
int N, M; cin >> N >> M;
std::vector<std::pair<int,int>> edges(M);
for(auto& e : edges){
cin >> e.first >> e.second;
}
SPQRTree spqrTree;
spqrTree.Initialize(N, edges);
cout << (spqrTree.components.size()) << '\n';
for(auto& c : spqrTree.components){
cout << SPQRTree::ComponentTypeString(c.ty) << ' ' << c.edges.size();
for(auto& e : c.edges){
cout << ' ' << spqrTree.edges[e].from << ' ' << spqrTree.edges[e].to;
}
cout << '\n';
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment