图论
拓扑序列
有向无环图一定存在拓扑序列，通过入度为0来判断该点是否可以加入队列。
强连通分量
定义： 在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量（Strongly Connected Components, SCC）。换句话说，一个强连通分量中的每两个点可以互相到达，且这个强连通分量所包含的的节点数尽可能大。
Tarjan算法可以寻找有向图的中强连通分量，将每一个强连通分量缩成一个点，就可以把有向图转化为DAG有向无环图（拓扑图）。
/*
变量解释：
dfn[N]是dfs序，也就是dfs访问每个结点的开始时间
low[N]，可以理解为某个结点可以通过后向边（back edge）或者横插边（cross edge）回到最开始的时间（回到之前的结点）。相当于形成了环，这棵子树就是一个强连通分量，子树的根结点是最早遍历的点
timestamp表示时间戳，用来给dfn[N]赋值
stk[N]是模拟栈，in_stk[N]标记结点是否已经加入栈中
scc_cnt记录强连通分量的数量，scc[N]记录每个结点所属的强连通分量。
vec[N]用来记录一个强连通分量中结点的数量（可以可无，根据题目要求灵活设置）
*/
int dfn[N],low[N],timestamp;
int stk[N],in_stk[N],top;
int scc_cnt,scc[N];
int vec[N];
void tarjan(int u){
//初始时结点开始访问的开始时间和可以回到某个结点（有最早开始时间）相同，也就是本身是一个强连通分量。
dfn[u]=low[u]=++timestamp;
//入栈
stk[++top]=u;
in_stk[u]=true;
//遍历邻边
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
//如果还未访问过就继续递归访问
//tree edge
tarjan(j);
//通过儿子结点的low[j]值来更新low[u]的，因为u->j
low[u]=min(low[u],low[j]);
}else if(in_stk[j]){
//如果碰到已经访问过的结点
//back edge
low[u]=min(low[u],dfn[j]);
}
}
//强连通分量子树的根结点
//两个值相等说明是强连通分量这棵子树的根结点（最高的结点）
// 解释一下为什么tarjan完是逆dfs序
// 假设这里是最高的根节点fa
// 上面几行中 fa的儿子节点j都已经在它们的递归中走完了下面9行代码
// 其中就包括 ++scc_cnt
// 即递归回溯到高层节点的时候 子节点的scc都求完了
// 节点越高 scc_id越大
// 在我们后面想求链路dp的时候又得从更高层往下
// 所以得for(int i=scc_cnt(根节点所在的scc);i;i--)开始
if(dfn[u]==low[u]){
scc_cnt++;
int ver;
do{
ver=stk[top--];//出栈
scc[ver]=scc_cnt;//保存每个点属于哪个强连通分量
vec[scc_cnt]++;//记录每个强连通分量集合
in_stk[ver]=false;
}while(ver!=u);
}
}
割点
定义： 对于一个无向图（可能不是一个连通图，有多个连通分量），如果把一个点删除后，图的连通分量增加，那么这个点就是这个图的割点
int n,m;
int dfn[N],low[N],timestamp;
bool flag[N]; //判断割点是否以及加入到答案中
vector<int> vec;//割点的答案
int root;//因为无向图不一定是连通图，所有要进行多次dfs,那么需要记录每次dfs的根节点
void tarjan(int u,int father){
dfn[u]=low[u]=++timestamp;
int child=0;//记录u结点在dfs搜索树中的孩子个数（原因下面会有解释）
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father)continue;
if(!dfn[j]){
//树边
child++;
tarjan(j,u);
low[u]=min(low[u],low[j]);
//low[j]>=dfn[u]表示j结点不可以到达比u更早访问的结点（祖先结点），也就是说如果u结点被删掉，
//那么j结点和u结点前面访问过的结点是是不连通的，满足割点的定义
if(u!=root && low[j]>=dfn[u] && !flag[u]){
flag[u]=true;
vec.push_back(u);
}
}else{
//非树边
low[u]=min(low[u],dfn[j]);
}
}
/*
这里root（dfs搜索树的根节点）需要单独判断。因为根比较特殊，如果child>=2，则表示root是一个割点。
如何解释呢？
在dfs搜索中，根节点是最后才回溯的，也就是说如果root有两个及以上的孩子，就表示其他的点都没能搜索到
root的孩子（导致root还需要继续搜索），那么如果删掉root，就会存在其他的点无法到达root的其中几个孩
子，所以root此时就是割点。
*/
if(u==root && child>=2 && !flag[u]){
vec.push_back(u);
flag[u]=true;
}
}
最短路
反向建图： 对于单源求最短路，可以直接使用Dijkstra或者spfa求解即可，对于多起点单终点的最短路问题，要计算每个起点到终点的最短距离，可以通过反向建图的方式，把起点和终点调换，这样就可以将问题转换为一个起点。
虚拟源点： 通过建立虚拟源点也可以将多起点转换为从虚拟源点出发的新图。
Dijkstra
我的理解： 图论求方案数就有一些DP的影子了。DP前面计算出的子问题的结果，后面基本上不会改变，而且会用到后续的求解中。而DP问题的求解需要求解的问题满足拓扑序。而bfs和dijkstra都是满足拓扑序的，以dijkstra为例，每次从优先队列中取出的点，表示已经达到最小值，后续不会再更新，然后用这个点更新邻边。
适用于边权都为非负数
朴素版Dijkstra算法
每次找到一个最小值，都会默认到该点的距离已经被更新至最小，所以用st数组进行标记，这也是Dijkstra算法的特点，利用贪心的思想，每次找到最短距离，就将这个点确定下来，不再更新。
const int N=510;
int g[N][N];
bool st[N];
int dist[N];//记录距离
int n,m;//n为点的个数，m为边的个数
int dijkstra(){
//初始化距离为最大值
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//找到距离的最小值
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[i] && (t==-1 || dist[t]>dist[j]))t=j;//找到距离的最短点
}
st[t]=true;
//更新距离最短点到其他点的最短距离
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
//如果是最大值则表示无法到达
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
堆优化版Dijkstra算法
堆优化版本在查找所有距离中的最小值时，使用的是堆，可以降低时间的复杂度。
const int N=2e5;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
//稀疏图用邻接表
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//用STL自带的优先队列存距离的值
priority_queue<PII,vector<PII>,greater<PII> > heap;//优先队列-小根堆
heap.push(make_pair(0,1));//将第一个点加入堆
while(!heap.empty()){
PII t=heap.top();//获得距离中的最小值
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver])continue;
st[ver]=true;
//更新最短距离
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push(make_pair(dist[j],j));//将新更新的距离加入堆
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
SPFA
SPFA可以用于有负权边的单源最短路问题，时间复杂度为O(km)，k一般是很小的常数，最坏情况下k=n,时间复杂度达到O(nm)。如果有负权回路的情况，则不能使用SPFA算法，否则会出现死循环。
算法流程： 因为SPFA是从源点开始，对于有发生松弛的点（就是最短距离发生改变），就会将其加入队列，算法结束的条件是队列为空，如果有负权回路，那么最短距离会永远有发生变化，那么队列中就会一直不为空。
SPFA判断是否存在负环，添加一个cnt数组统计两点之间边的个数（与松弛的次数有关），如果数量>=n，则表示一定存在负环。求最短路时，图中不能有负环，同理求最长路时，图中不能有正环，可以将求解过程替换成求最长路，就可以判断图中是否有正环。
int dist[N];
bool st[N];//st数组的用法与Dijkstra不同，这里是判断队列中是否会加入重复的点。
int que[N];
int spfa(){
//初始化距离
memset(dist,0x3f,sizeof dist);
dist[1]=0;
int hh=0,tt=0;
que[0]=1;//加入队列
st[1]=true;
while(hh<=tt){
int t=que[hh++];//取出
st[t]=false;
//更新距离
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
//如果没有在队列中就加入队列
if(!st[j]){
que[++tt]=j;
st[j]=true;
}
}
}
}
return dist[n];
}
SLF优化：Small Label First策略，顾名思义，小的值放前面。使用STL中的双端队列deque容器来实现，在松弛后加入队列前，对要加入队列的点 u，如果 dist[u] 小于队头元素 v 的 dist[v]，将其插入到队头，否则插入到队尾。
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
st[j]=true;
//与队头元素进行比较，小于队头元素插入到队头，大于队头元素插入到队尾
if(que.size() && dist[j]<dist[que.front()]){
que.push_front(j);
}else que.push_back(j);
}
}
差分约束
差分约束就是把不等式的约束，求解自变量的最大值或最小值，转化为单源最短路或最长路的求解。
如何求最大值或最小值，这里的最值指的是每一个变量的最值。
能够这样子转化是因为该不等式约束刚好和最短路求解中的松弛操作对应
注意：
-
对于不同的题目，求解的变量可能并不是直接以xi的形式给出，而是需要自己构造，然后再寻找自己构造的变量的约束，进行最长路或最短路的求解。
-
在利用最短路求解前，要判断是否存在一个点，能够通过边到所有点，因为这样才有可能是有解的，否则需要加入虚拟源点。然后判断是否有负环。不能从任意点判断是否有负环，因为从某些点出发可能到达不了负环
-
源点需要满足的条件：从源点出发，一定可以走到所有边，因为每一条边表示是的一个约束条件，只有所有边都能走到，才能表示这个约束被考虑到了。如果不存在负环，就说明有解。找能走到所有边的源点只是为了判断有没有解，正式求解的时候不一定要从这个源点出发！！！
Floyd
可以处理负权
const int N=210;
int dist[N][N];
//floyd算法
void floyd( ){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
}
//dist数组初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)dist[i][j]=0;//存在自环直接就删掉
else dist[i][j]=INF;//初始化为最大值
}
}
//因为可能存在负权边的情况，所以当两个点之间的距离无解时，可能距离并不是初始化的正无穷，而是会小一点点。
//所以用>INF/2来判断是否是无解。
if(dist[x][y]>INF/2)cout<<"impossible"<<endl;
else cout<<dist[x][y]<<endl;
最小生成树
prim
朴素prim算法
时间复杂度为O(n^2)，可以使用堆优化，和Dijkstra一样用优先队列代替对，优化prim算法时间复杂度为O(mlogn)，适用于稀疏图，但是稀疏图的时候求最小生成树，Kruskal更加实用。
int prim(){
int res=0;
memset(dist,0x3f,sizeof dist);
//把第一个点加入集合
dist[1]=0;
for(int i=0;i<n;i++){
//找到到集合距离最短的
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[t]>dist[j]))t=j;
}
if(dist[t]==0x3f3f3f3f)return dist[t];
st[t]=true;
res+=dist[t];
//更新点到集合的距离
for(int j=h[t];~j;j=ne[j]){
if(dist[e[j]]>w[j]){
dist[e[j]]=w[j];
}
}
}
return res;
}
堆优化版prim算法
typedef pair<int,int> PII;
const int N=110;
int n;
int map[N][N];
int dist[N];
bool st[N];
int prim(){
int res=0;
memset(dist,0x3f,sizeof dist);//初始化距离
//创建优先队列
priority_queue<PII,vector<PII>,greater<PII> > heap;
dist[1]=0;
heap.push(make_pair(0,1));//将第一个点加入优先队列
while(heap.size()){
//取出距离的最小值
PII t=heap.top();
heap.pop();
//更新到集合的距离
int ver=t.second;
if(st[ver])continue;//因为可能存在一个点被多次加入优先队列的情况，所以如果已经
st[ver]=true;
res+=t.first;
for(int i=1;i<=n;i++){
if(!st[i]){
if(dist[i]>map[ver][i]){
dist[i]=map[ver][i];
heap.push(make_pair(dist[i],i));
}
}
}
}
return res;
}
Kruskal
时间复杂度为O(mlogm)
对边进行判断，首先对每一条边升序进行排序，然后遍历每一条边，加入生成树，如果最后生成树的边数=n-1，则表示生成树存在。
判断新加入的边是否构成环，可以通过并查集来维护一个集合。
kruskal算法可以求解多个连通块最小生成树，因为是对边进行操作，每次把边加入最小生成树集合，但是并不能保证最后的最小生成树是个连通图（可能有多个最小生成树），所以最后还需要判断一下最小生成树边的数量cnt和点的数量n的关系，cnt=n-1则表示最后的最小生成树是一个连通图。
const int N=1e5+10,M=2e5+10;
int n,m;
int res;
struct line{
int u;//起点
int v;//终点
int w;//权重
//升序排序
bool operator < (const line& t){
return this->w<t.w;
}
}line[M];
int pre[N];
//并查集查找
int find(int x){
if(pre[x]!=x) pre[x]=find(pre[x]);
return pre[x];
}
bool kruskal(){
int cnt=0;
//尝试加入每一条边
for(int i=0;i<m;i++){
int pa=find(line[i].u);
int pb=find(line[i].v);
if(pa!=pb){
res+=line[i].w;
pre[pa]=pb;
cnt++;
}
}
if(cnt<n-1){
return false;
}
return true;
}
严格次小生成树求解
次小生成树：在最小生成树的基础上，替换掉最小生成树上的边，使得生成树的权重和变成第二小的
求解流程：
-
求解最小生成树，并将求解出来的最小生成树建图
-
利用dfs求解最小生成树中，点与点之间的路径中，边的权重的最大值和次大值
void dfs(int u,int father,int max2,int max1,int d2[],int d1[]){ d1[u]=max1,d2[u]=max2; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(j==father)continue; int m1=max1,m2=max2; //只有严格大于才可以替换 if(w[i]>m1){ m2=m1; m1=w[i]; }else if(w[i]<m1 && w[i]>m2) m2=w[i]; dfs(j,u,m2,m1,d2,d1); } } -
遍历非树边（也就是没有被最小生成树选中的），判断该非树边（x,y,w）是否可以替换最小生成树（u,v）路径上权重最大的边。只有w大于权重最大的边才可以替换，因为这样满足最小生成树的求解过程。注意： 步骤2之所以还求解次大值的原因，可能存在w与最大边相同的情况，这样就需要替换次大边。有没有可能w小于最大边，大于次大边的情况呢？ 不可能，因为如果存在w小于最大边，而大于次大边，那么w这条边就可以作为最小生成树的一条边，那么就与步骤1求解的最小生成树矛盾了。
for(int i=0;i<m;i++){ if(edge[i].flag)continue; int u=edge[i].u,v=edge[i].v,w=edge[i].w; if(w>dist1[u][v]){ res=min(res,sum-dist1[u][v]+w); }else if(w==dist1[u][v]){ res=min(res,sum-dist2[u][v]+w); } }利用倍增的思想求解严格次小生成树
-
求解最小生成树，并将求解出来的最小生成树建图。
-
利用倍增的思想，在最近公共祖先求解每个点向上2j个单位的父节点时，同时维护向上2j个单位的路径上权重的最大值和次大值。这里维护的二进制长度的最大值和次大值
void dfs(int u,int father,int dist){ depth[u]=depth[father]+1; f[u][0]=father; d1[u][0]=dist,d2[u][0]=-INF; for(int i=1;i<=17;i++){ int mid=f[u][i-1];//记录中间节点 f[u][i]=f[mid][i-1]; //把四个极值都取出来，然后遍历找到最大值和次大值 int dist[]={d1[u][i-1],d2[u][i-1],d1[mid][i-1],d2[mid][i-1]}; for(int k=0;k<4;k++){ int w=dist[k]; if(w>d1[u][i]){ d2[u][i]=d1[u][i]; d1[u][i]=w; }else if(w<d1[u][i] && w>d2[u][i])d2[u][i]=w; } } //遍历邻边 for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(j==father)continue; dfs(j,u,w[i]); } } -
最后遍历非树边，找lca（最近公共祖先）的时候，同时记录每次跳跃路径上的最大值和次大值。
int get_lca(int a,int b,int w){ if(depth[a]<depth[b]) return get_lca(b,a,w); static int distance[N*2];//路径a,b上所有的最大值和次大值 int cnt=0; for(int i=17;i>=0;i--){ if(depth[f[a][i]]>=depth[b]){ distance[cnt++]=d1[a][i]; distance[cnt++]=d2[a][i]; a=f[a][i]; } } if(a!=b){ for(int i=17;i>=0;i--){ if(f[a][i]!=f[b][i]){ distance[cnt++]=d1[a][i]; distance[cnt++]=d2[a][i]; distance[cnt++]=d1[b][i]; distance[cnt++]=d2[b][i]; a=f[a][i],b=f[b][i]; } } distance[cnt++]=d1[a][0]; distance[cnt++]=d1[b][0]; } //找到最大值和次大值 int m1=-INF,m2=-INF; for(int i=0;i<cnt;i++){ if(distance[i]>m1){ m2=m1; m1=distance[i]; }else if(distance[i]<m1 && distance[i]>m2){ m2=distance[i]; } } if(w>m1)return w-m1;//非树边权重大于最大值，可以替换 if(w>m2)return w-m2;//非树边权重等于最大值，大于次大值，可以用次大值替换 return INF; }
-
最近公共祖先-LCA
朴素版求解公共祖先
首先令深度深的一端结点先移动，移动到相同深度后，然后同时往上移动，知道找到相同的结点，即为找到公共祖先。
时间复杂度: 时间复杂度为O(nlogn)，如果是链状的二叉树，时间复杂度为O(n^2)
//获得最近公共祖先
int get_lca(int a,int b){
if(dist[a]<dist[b])return get_lca(b,a);
//将两个点移动至同一个深度
while(dist[a]>dist[b]) a=f[a];
//同时向上移动
while(a!=b){
a=f[a];
b=f[b];
}
return a;//返回公共祖先
}
基于倍增求解公共祖先
在朴素版求解中，结点每次都是移动一个单位，时间复杂度高。而基于倍增的思想，每次移动2^j 个距离单位，所以我们构造了一个f(i)(j)数组，表示从结点i出发，向上移动2^j所到达的结点编号。 在预处理f数组时，也用到了动态规划的思想
//dfs求解点的深度+倍增求解父节点
//dfs代码少一点，就是可能会有爆栈的风险
void dfs(int u,int father){
depth[u]=depth[father]+1;
f[u][0]=father;
for(int k=1;k<=16;k++)f[u][k]=f[f[u][k-1]][k-1];//倍增计算父节点
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father)continue;
dfs(j,u);
}
}
int n,m;
int dist[N];//深度
int que[N];
int f[N][16];
//计算点到根结点的距离
void bfs(int root){
memset(dist,0x3f,sizeof dist);
//在这里有一个技巧，就是将根节点dist[root]=1，dist[0]=0;这样可以完美的避开边界问题，就是在进行LCA时，会出现结点一步走过 //头的情况，按理说如果走过头，结点不能进行跳跃，如果将dist[root]=0，那么在判断dist[f[a][i]]>=dist[b]时，就会可能成立
//结点就会进行跳跃（当b是根结点时，dist[root]=0，条件就会成立）。
dist[root]=1,dist[0]=0;
int hh=0,tt=0;
que[0]=root;
while(hh<=tt){
int t=que[hh++];
//遍历临边
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
//cout<<"j"<<j<<endl;
if(dist[j]>dist[t]+1){
dist[j]=dist[t]+1;
que[++tt]=j;//加入队列
//p[j]=t;//记录父节点
//计算2^k步所能到的结点
//利用bfs求解深度时，可以顺带预处理f数组，因为每一层的f数组计算只与前几层已经计算过的值有关
//就比如计算f[j][1]=f[f[j][0]][k-1]，而f[j][0]一定在bfs搜索第一层的时候已经计算出来了。
f[j][0]=t;//k=0表示走一步
for(int k=1;k<=15;k++){
f[j][k]=f[f[j][k-1]][k-1];
}
}
}
}
}
//获得最近公共祖先
int get_lca(int a,int b){
if(dist[a]<dist[b])swap(a,b);
//一个结点往上走，从大到小
for(int i=15;i>=0;i--){
if(dist[f[a][i]]>=dist[b])a=f[a][i];
}
if(a==b)return a;
//同时向上移动
for(int i=15;i>=0;i--){
//如果结点不相同，表示最近公共祖先还在上面，可以跳上去。
//如果结点相同，表示找到公共祖先，但可能不是最近公共祖先，最近公共祖先可能在偏下的位置，所以不需要跳上去。
if(f[a][i]!=f[b][i]){
a=f[a][i];
b=f[b][i];
}
}
//假设a、b距离lca的层数为10，在i=3时，f[a][i]!=f[b][i]，a和b跳了上去。在i=1时，f[a][i]=f[b][i],表示找到
//公共祖先，虽然我们肉眼可以知道已经到达最近公共祖先了，但是程序并不知道，程序会认为最近公共祖先可能还在下面的位置
//所以不需要跳跃上去。在i=0时，f[a][i]!=f[b][i]，a和b跳跃上去，最近公共祖先的距离为1。
//不管是否能够一次跳跃刚好能到达最近公共祖先，程序总是会在最近公共祖先的前一个位置停下。
return f[a][0];
}
二分图
二分图说人话定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。
最小点覆盖： 这个概念针对任意的无向图都是成立的。是指我们从图中选出最少的点集，使得所有的边中的两个端点至少有一个端点在该点集中。而在二分图中，最小点覆盖n==最大匹配数m。
最大独立集： 这个概念对任意无向图都是成立的，选出最多的点集，使得点集的内部没有边相连。
在二分图中，最大独立集==图中总结点数量n-最小点覆盖m。简单证明：最小点覆盖是选出最少的点集，使得这些点集能覆盖所有边，那么将这些点去除，那么剩下来的点中内部就没有边了，也就是我们要求解的最大独立集。
染色法
染色法判断是否为为二分图，时间复杂度O(n + m)
染色技巧： 就是给定的一个原题并不是一个二分图，但是我们可以通过加一些判断来隐藏掉一部分边，，然后判断子图是否为二分图。
dfs染色法
bool dfs(int u,int c){
color[u]=c;
//给邻边染色
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!color[j]){
if(!dfs(j,3-c)){
return false;
}
}else{
//颜色与邻边相同
if(color[j]==color[u]){
return false;
}
}
}
return true;
}
bfs染色法
bool bfs(int u,int c){
color[u]=c;
int hh=0,tt=0;
que[0]=make_pair(u,c);
while(hh<=tt){
PII t=que[hh++];
int ver=t.first,col=t.second;
//遍历邻边加入队列
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(!color[j]){
color[j]=3-col;
que[++tt]=make_pair(j,3-col);//加入队列
}else{
//与邻边颜色相同
if(color[j]==color[ver]){
return false;
}
}
}
}
return true;
}
二分图的最大匹配
说人话定义：二分图左右两端的点集，左右点集的点与点之间，每个点只连接一个点（一对一匹配）。然后最大匹配就是使一对一匹配的数量最多
匈牙利算法
涉及到递归的思想，男生2找到自己匹配的女生1，如果这个女生1已经匹配了男生1，那么男生1就要去判断是否有别的女生可以选择，如果有，那么男生2就可以选择女生1，皆大欢喜（这样才有最大匹配）。如果男生1在查找的过程中碰到男生3已经选择的自己心仪的女生，那么男生3就要继续去查找（递归思想）
首先利用要利用匈牙利算法的前提是这个图是一个二分图，且二分图的点集能够区分，许多题目比较隐蔽，不容易看出是一个最大匹配问题，比如Awing372.棋盘覆盖。
const int N=510,M=1e5+10;
int h[N],e[M],ne[M],idx;
int n1,n2,m;
bool st[N];//每次遍历左端点集的时候，都要初始化st
int match[N];//女生匹配的男生编号（右端匹配的左端编号）
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool find(int u){
//遍历邻边
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
st[j]=true;
//如果这个女生还没有找到匹配的男生 或者 匹配的男生可以找到新的女生
if(match[j]==0 || find(match[j])){
match[j]=u;
return true;
}
}
}
return false;
}
欧拉回路和欧拉路径
定义：
欧拉回路： 通过图中每条边恰好一次的回路。
欧拉通路： 通过图中每条边恰好一次的通路。
欧拉图： 具有欧拉回路的图。
半欧拉图： 具有欧拉通路但不具有欧拉回路的图。
对于无向图：存在欧拉路径的充要条件 : 度数为奇数的点只能有0或2个。存在欧拉回路的充要条件 : 度数为奇数的点只能有0个
对于有向图：存在欧拉路径的充要条件 : 要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度入度 剩余的两个点:一个满足出度-入度1(起点) ，一个满足入度-出度==1(终点)。存在欧拉回路的充要条件 : 所有点的出度均等于入度。
环计数
无向图三元环计数
算法步骤：
-
首先需要对无向边按照一定规则定向，设d[u]表示u节点的度数。如代码所示，此时这张图是一张有向无环图
度数大的向度数小的连边，度数相同的话，编号小的向编号大的连边。
if(d[u]>d[v]) add(u,v); else if(d[u]==d[v] && u<v) add(u,v); else add(v,u); -
枚举每一个点u作为三元环的起点，然后标记u的所有出点v，再枚举所有v的出点w，如果w已经被v标记过，则表示此时形成三元环。
代码如下：
时间复杂度：O(m*m1/2) m为边的数量
int ans=0;//三元环计数
//遍历每个点
int cnt=0;
for(int u=1;u<=n;u++){
cnt++;//标记
for(int i=h[u];~i;i=ne[i])flag[e[i]]=cnt;//对所有u的出点进行标记
//枚举u的出点v
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
//枚举v的出点w
for(int k=h[j];~k;k=ne[k]){
int ver=e[k];
if(flag[ver]==cnt)ans++;//表示已经被标记过，形成三元环。
}
}
}