复习图论

1.单源最短路问题

Dijkstra 原版O(n^2)==>堆优化O(nlogn+m) 利用边权都是正的，所以路径会不断增长，单源最短路==>每次考虑能从源点到达的最近未访问结点就行了，找到的最短路是升序。（但如果有负边的话，就不能保证是升序了，所以错）

Bellman-Ford其实就是Dijkstra的暴搜，解决负边的问题

SPFA 优先队列O(km)不需要建vis数组，只要能松弛就push，所以解决了负边问题

Floyd: 动态规划d[i][j] = min(d[i][j],d[i][k]+d[k][j]) O(n^3)

2.图的遍历

dfs和bfs复杂度相同：

邻接矩阵：O(n^2)

邻接表：O(m)

【本质是数据结构决定的访问边的方式不同】

3.拓扑排序 O(m)

一遍dfs，标黑的同时（出度为0）把顶点压到栈中

4.Tarjan LCA O(m)

关键是引入了并查集，思路是遍历所有询问保证每次询问被回答时是正确的。

p[u]=u

p[v]=u //这里说的是跟v的公共祖先是v的询问（即另一个顶点是v的子代）已经回答过了，去考虑与v的公共祖先是u的询问（u是v的祖先）

5.Tarjan SCC O(m)

维护prev，low和一个stack

prev[u]==low[u]代表u是一个强连通分量的root【因为low[u]表示从“以u为根的子树中的结点”所能到达的最早的节点的prv[]，如果自己最早能到的是自己那代表有一条边能指回来形成环或者没有子代】

B边（返祖边）是造成SCC的原因

可以试试看这个：https://www.bilibili.com/video/av18360382?from=search&seid=2575165341484629919

习题：洛谷P3387 【模板】缩点

 1 #include<iostream>
 2 #include<vector>
 3 #include<stack>
 4 #include<queue>
 5 #include<map>
 6 using namespace std;
 7 
 8 int a[10005],prev[10005],low[10005],instack[10005];//score[i]是新的点权 
 9 
10 vector<int> edge[10005],bian[10005];
11 stack<int> s;
12 queue<int> q;//先进先出 
13 map<int,int> scc;// m[i]代表i所在的联通分量
14 
15 int indegree[10005],m1[100005],m2[100005],score[10005],ans,time;
16 
17 void tarjan(int u){
18     prev[u] = low[u] = ++time;//low[u]代表以u为根的子树中（包括u）所能达到的prev最小的值
19     s.push(u); instack[u]=1;//每个点都是SCC的一部分 
20     for(int i=0;i<edge[u].size();i++){
21         int v = edge[u][i];
22         if( prev[v]==0 ) {
23             tarjan(v);
24             low[u] = min( low[u],low[v] );
25         }
26         else if( instack[v] ){//指向祖先，如果不是祖先那一定出栈了 
27             low[u] = min( low[u],prev[v] );//u可能指向多个祖先 【low的定义就是当前节点所能达到的最浅的层数，所以要用min不停迭代】 
28         }
29     }
30     if( prev[u]==low[u] ){
31         while( s.top()!=u ) {
32             int node = s.top(); instack[node]=0; s.pop(); score[u]+=a[node]; scc[node]=u; 
33         }
34         instack[u]=0; s.pop(); score[u]+=a[u]; scc[u]=u;
35     } 
36     
37 }
38 
39 int dfs(int u){
40     if(bian[u].size()==0) return score[u];
41     int count=0;
42     for(int i=0;i<bian[u].size();i++){
43         int v= bian[u][i];
44         count = max(count,score[u]+dfs(v));
45     }
46     return count;
47 }
48 
49 int main(){
50     int n,m; cin>>n>>m;
51     for(int i=1;i<=n;i++) cin>>a[i];
52     for(int i=1;i<=m;i++){
53         int u,v; cin>>u>>v;
54         edge[u].push_back(v);
55         m1[i]=u; m2[i]=v;
56     }
57     
58     for(int i=1;i<=n;i++){
59         if( prev[i]==0 ) tarjan(i);//以i为根的搜索树缩点 
60     }
61 
62     //重新建图
63     //扫一遍原图中的所有边，如果该边对应的两个点在同一个scc中，不用建边；否则，在两个scc间建一条有向边。转化为DAG     
64     for(int i=1;i<=m;i++){
65         if( scc[ m1[i] ] == scc[ m2[i] ] ) continue;
66         else {
67             bian[ scc[m1[i]] ].push_back( scc[m2[i]] );
68             indegree[ scc[m2[i]] ]++;
69         }
70     }
71     
72     //搜索所有入度为0的顶点
73     for(int i=1;i<=n;i++){
74         if(indegree[i]==0) ans=max( ans,dfs(i) );
75     }
76     
77     cout<<ans;
78     
79     return 0;
80 }

6. Tarjan桥和割点 O(m)

思路跟求scc差不多

5.最小生成树

Prim O(n^2) 每次要n代价搜一遍找最小的边

这么做保证了不会形成环【与dijkstra不同的是dijkstra每次是更新一条最短路径】

Kruskal O(mlogm) 如果不成环就每次加最短的边（节约了prim里的n代价找最小边，但要sort一遍所有边）