圖論
===
###### tags: `Algorithm`

## dijkstra
>[pf](https://blog.csdn.net/softee/article/details/39034129)
>[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/ShortestPath/Dijkstra.cpp#L15)

## bellmanford
>[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/ShortestPath/Bellman-Ford.cpp)

// Bellman-Ford
// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define maxN 100005
#define pb push_back
typedef pair < int, int > pii;

vector < pii > edges[maxN];
int dis[maxN];

inline void BellmanFord ( int start ){
	memset ( dis, 0x3f3f3f, sizeof dis );
    dis[start]=0;
	queue < int > q;
	q.push ( start );
	while ( !q.empty() ){
		int now = q.front();
		q.pop();
		for ( auto i: edges[now] ){
			if ( dis[i.first] > dis[now] + i.second ){ // 檢查是否能更新
				q.push ( i.first );
				dis[i.first] = dis[now] + i.second;
			}
		}
	}
}

## SPFA
https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/ShortestPath/SPFA.cpp

// SPFA
// basic on Bellman-Ford
// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define maxN 100005
#define pb push_back
typedef pair < int, int > pii;

vector < pii > edges[maxN];
int dis[maxN];
bool inQueue[maxN]; // 紀錄是否已經在queue中

inline void SPFA ( int start ){
	memset ( dis, 0x3f3f3f, sizeof dis );
    dis[start]=0;
	queue < int > q;
	q.push ( start );
	inQueue[start] = true;
	while ( !q.empty() ){
		int now = q.front();
		q.pop();
		inQueue[now] = false; // 紀錄已經取出
		random_shuffle ( edges.begin(), edges.end() );//打亂順序 有些測資會故意讓算法爆掉
		for ( auto i: edges[now] ){ // 跑過所有可以被now連結到的點
			if ( dis[i.first] > dis[now] + i.second ){
				dis[i.first] = dis[now] + i.second;
				if ( !inQueue[i.first] ){
					// 如果點沒有在queue中，再加入queue，並記錄已經在queue中
					inQueue[i.first] = true;
					q.push ( i.first );
				}
			}
		}
	}
}

## SLF
[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/ShortestPath/SPFA-buff-SLF.cpp)

## LLL
[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/ShortestPath/SPFA-buff-LLL.cpp)

## Floyd-warshall
[code]
(https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/ShortestPath/Floyd_Warshall.cpp)

## 最小生成樹
>[ref1](http://alrightchiu.github.io/SecondRound/minimum-spanning-treeintrojian-jie.html)
>[**ref2**](https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/zui-xiao-sheng-cheng-shu)
>[演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html)
:::info
* 生成樹:從一張圖取出一棵樹，包含圖上所有點。可能有許多種。
* 如果圖不連通,則可以求出最小生成森林
* 最小生成樹: 權重最小的生成樹
:::

### kruskal

// Kruskal
// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define maxN 10005
#define pb push_back
typedef pair < int, int > pii;

int dis[maxN];

inline void init ( void ){
	for ( int i = 0 ; i < maxN ; i++ )
		dis[i] = i;
}

inline int find ( int a ){
	return dis[a] == a ? a : dis[a] = find ( dis[a] );
}

inline void Union ( int a, int b ){
	dis[find ( a )] = find ( b );
}

inline bool same ( int a, int b ){
	return find ( a ) == find ( b );
}

struct node{
	int u, v, w;
};

inline bool cmp ( node a, node b ){
	return a.w < b.w;
}

vector < node > edges;
vector < pii > mst[maxN];

inline void Kruskal ( void ){
	sort ( edges.begin(), edges.end(), cmp );
	for ( auto i: edges ){ // C++ 11寫法，不懂再來問
		if ( same ( i.u, i.v ) )
			continue;
		Union ( i.u, i.v );
		mst[i.u].pb ( pii ( i.v, i.w ) );
		mst[i.v].pb ( pii ( i.u, i.w ) );
	}
}

* dsu
### Prim
不斷找最小的邊
>[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/MST/Prim.cpp)

## LCA
:::info
最低共同祖先
:::
#### 倍增法
:::info
* 轉移方程
fa[i][j] = fa[fa[i][j-1]][j-1];
`i` :節點
`j` :i的第2^j倍祖先

:::
>[ref](https://www.itread01.com/content/1542612733.html)

## Tarjan 尋找割點

* Tree edge：若vertex(Y)是被vertex(X)「發現」，則edge(X,Y)即為Tree edge，也就是Depth-First Tree中的edge。
* 透過顏色判斷edge：當vertex(X)搜尋到vertex(Y)，且vertex(Y)為「白色」時，就會建立出Tree edge。
* Back edge：所有指向ancestor的edge，稱為Back edge。如圖六中，edge(F,B)與edge(H,G)。
* 透過顏色判斷edge：當vertex(X)搜尋到vertex(Y)，且vertex(Y)為「灰色」，就會建立起Back edge，見圖三(j)、圖三(q)與圖六。


1. DFS的根節點有超過一條tree edge ,根節點必為AP
2. DFS 的任意非根節點 u 的子樹們沒有BackEdge通往 u 的祖先們時, u 必為AP
* D[u]<=L[u],u!=root
D(u) DFS時深度
L(u) 子樹們的最低深度

* 尋找 L(u)
*

>[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/AP/Tarjan-AP.cpp)
>[ref](http://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html)
>[ref](https://fsh0524.github.io/2016/03/03/Articulation-Point/)

## Tarjan's SCC
>[code](https://github.com/MiohitoKiri5474/Codes/blob/master/C%2B%2B/templates/SCC/Tarjan.cpp)

## 樹鏈
1.取得最大的子樹