图论-二分图相关

定义 二分图又称作二部图,是图论中的一种特殊模型。 设\(G=(V,E)\)是一个无向图,如果顶点\(V\)可分割为两个互不相交的子集\((U,V)\),并且图中的每条边\((i,j)\)所关联的两个顶点\(i\)和\(j\)分别属于这两个不同的顶点集,则称图\(G\)为一个二分图。

Continue reading

数据结构-ST表

定义 范围最值查询问题(Range Minimum Query,RMQ):给定一个数组\(A[1\ldots n]\),询问若干次:指定\(i\)和\(j\),计算\(min\{A[i],A[i+1],\ldots ,A[r]\}\)或\(max\{A[i],A[i+1],\ldots ,A[r]\}\)。 ST表是解决RMQ问题的一种数据结构。

Continue reading