NOIP考前攒rp。
图论是是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。（这段话是摘抄的）
DFS(Depth First Search)
深度优先搜索，是处理很多问题是需要使用的方法，有时也是用来获得部分分的利器，一大特点就是递归调用其本身，也就是使用栈实现。
typename dfs(int u,...)
{
if(conditions) return ...;
give Tag;
for(v to u)
{
if(visited) continue;
dfs(v);
details;
}
return ...;
}
DFS遍历而形成的树叫做DFS树，DFS树没有横插边。
BFS(Breadth First Search)
广度优先搜索，优先访问当前层的节点，一般使用队列实现。
typename bfs(int start_point,...)
{
queue<typename> Q;
Q.push_back(strat_point);
details;
while(!Q.empty)
{
u=Q.front();
details;
for(v to u)
{
if(visited) continue;
details;
Q.push_back(v);
}
}
return ...;
}
树上问题
树的直径
树的直径是指树上任意两点间最长的简单路径。
两次DFS
第一次随机选择一个点，找到距离它最远的节点；再从这个节点为起点，到它深度最深的点。以这两个节点为端点的简单路径就是树的直径。
优势：实现简单
树形DP
首先假定一个点为根，对于每一个节点，维护以它为根的子树内，经过根的最长路径和从叶子到根的最长路径，然后进行转移。
优势：可以进行修改，实现更丰富。
最近公共祖先 LCA
倍增跳写法
对于每个节点。维护它的所有 \(2^i\) 级祖先 \(i=0,1\dots \log n\) 。查找两个点的祖先时，先将深度大的节点跳到和深度小的节点深度相同，让后两个节点同时向上跳找lca。
算法时间复杂度 \(O(n\log n+Q\log n)\) ，空间复杂度 \(O(n\log n)\) 。
树剖写法
首先对整棵树进行重链剖分，当询问的两个节点不在同一条链的时候，选择链顶深度更深的那个节点，跳到链顶的父亲，重复此过程直到在同一条链中，返回深度更小的点。
算法时间复杂度 \(O(n+Q\log n)\) ，空间复杂度 \(O(n)\) 。
ST表写法
对整个树进行一次 \(dfs\) ，按照访问顺序将它以深度为第一关键字，节点为第二关键字变成长度为 \(2n\) 的序列，对这个序列预处理ST表。每次询问极为查询区间最小值的第二关键字。
算法时间复杂度 \(O(n\log n+Q)\) ，空间复杂度 \(O(n\log n)\) 。
LCT写法（基本上没有这样的吧）
每个节点存储以深度为第一关键字，编号为第二关键字的二元组，每次查询一条链上最小值的第二关键字。
算法时间复杂度 \(O(n+Q\log n)\) ，空间复杂度 \(O(n)\) 。
树的重心
对于某一个节点，如果它每一个子树的大小均不超过树大小的一般，这个点就是树的重心。
dfs求重心
DFS是维护每个子树的大小，就可以得到以每个节点为根时的所有子树大小，然后判断即可。
算法时间复杂度 \(O(n)\) 。
最小生成树
一个无向图图边权和最小的生成树成为最小生成树。
Kruskal算法
对所有的边进行排序，依次加入最小的边，同时用并查集维护图的连通性。
算法复杂度 \(O(m\log m+m \log n)\) 。
Prim算法
首先选择一个点，然后依次向这个连通块内加入到这个连通块距离最短的点即可。
使用堆维护，复杂度为 \(O(n\log n+m\log n)\) 。
最短路
Floyd 算法
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=0;
for(int i=1;i<=m;i++) f[l[i].u][l[i].v]=f[l[i].v][l[i].u]=l[i].len;
for(int k=1;k<=n;k++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
f[u][v]=min(f[u][v],f[u][k]+f[k][v]);
SPFA
struct edge{
int poi,len;
};
vector<edge> e[MAXN];
queue<int> Q;
int dis[MAXN],cnt[MAXN],vis[MAXN];
bool SPFA(int s)
{
memset(dis,0x3f,sizeof(dis));
int u=0;
dis[s]=0,vis[s]=true;
Q.push(s);
while(!Q.empty())
{
u=Q.front();
Q.pop(),vis[u]=false;
for(int k=0,lim=e[u].size(),v,w;k<lim;k++)
{
v=e[u].poi,w=e[u].len;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n) return false;
if(!vis[v]) Q.push(v),vis[v]=true;
}
}
}
return true;
}
Dijkstra 算法
typedef pair<int,int> pr;
vector<pr> e[MAXN];
long long dis[MAXN];
bool vis[MAXN];
priority_queue<pr,vector<pr>,greater<pr> > Q;
void Dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
Q.push(make_pair(0,s));
while(!Q.empty())
{
int u=Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u]=true;
for(auto ed:e[u])
{
int v=ed.first,len=ed.second;
if(dis[v]>dis[u]+len)
{
dis[v]=dis[u]+len;
Q.push(make_pair(dis[v],v));
}
}
}
return;
}