# 图论

# 1. 拓扑排序（ Kahn 算法）

	const int N = 1505;
	vector<int> e[N], tp;
	int d[N]; // 存每个点的入度
	bool topo(int n)
	{
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
	if (!d[i])
	q.push(i);
	}
	while (!q.empty())
	{
	int u = q.front();
	tp.push_back(u);
	q.pop();
	for (auto i : e[u])
	{
	d[i]--;
	if (!d[i]) // 入度为 0，压入队列
	q.push(i);
	}
	}
	if (tp.size() == n)
	return 1;
	else
	return 0;
	}
	void solve()
	{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
	int u, v; // 从 u 指向 v 有边
	e[u].push_back(v), d[v]++;
	}
	topo(n); // 是 1 是无环，可以输出拓扑序列，是 0 则有向图有环
	}

时间复杂度： $O（n+m）$

# 2. 迪杰斯特拉最短路

	#define int long long
	#define INF LLONG_MAX
	const int N = 1505;
	struct node
	{
	int v, w; // 点边的长度（权）
	};
	vector<node> e[N];
	int dis[N]; // 存每个点到 s 点的最短距离
	bool vis[N];
	int n, m;
	void dij(int s) // 找从 s 点开始到每个点的最短距离
	{
	for (int i = 0; i <= n; i++)
	dis[i] = INF;
	dis[s] = 0;
	for (int i = 1; i < n; i++)
	{
	int u = 0;
	for (int j = 1; j <= n; j++)
	{
	if (!vis[j] && dis[u] > dis[j]) // 找一个距离 s 点最近且没有被访问过的点
	u = j;
	}
	vis[u] = 1;
	for (auto i : e[u]) // 访问这个 u 点的每个邻点
	{
	if (dis[i.v] > dis[u] + i.w)
	dis[i.v] = dis[u] + i.w;
	}
	}
	}
	void solve()
	{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
	int u, v, w; // u 和 v 之间有长度为 w 的边
	cin >> u >> v >> w;
	e[u].push_back({v, w});
	e[v].push_back({u, w});// 无向图时写
	}
	}

时间复杂度：O（ $n^2$ ）

大根堆优化版本：

(大根堆堆顶是最大的元素！)

#define int long long
#define INF LLONG_MAX
const int N = 1505;
struct node
{
    int v, w; // 点 边的长度（权）
};
vector<node> e[N];
int dis[N]; // 存每个点到s点的最短距离
bool vis[N];
int n, m;
void dij(int s) // 大根堆优化版
{
    for (int i = 1; i <= n; i++) // 初始化
        dis[i] = INF, vis[i] = 0;
    dis[s] = 0;
    priority_queue<pair<int, int>> q; // first存值用于排序，second为结点
    // priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; 小根堆定义方法补充
    q.push({0, s});
    while (!q.empty())
    {
        auto ed = q.top();
        q.pop();
        if (vis[ed.second])
            continue;
        vis[ed.second] = 1;
        for (auto i : e[ed.second])
        {
            if (dis[i.v] > dis[ed.second] + i.w)
            {
                dis[i.v] = dis[ed.second] + i.w;
                q.push({-dis[i.v], i.v}); // 大根堆，正距离的相反数越大，实际距离越小，堆顶元素为距离s最近的结点
            }
        }
    }
}
void solve()
{

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w; // u和v之间有长度为w的边
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w}); // 无向图时写
    }
}

时间复杂度：O（ $mlogn$ ）

# 3. 贝尔曼 - 福特（Bellman-Ford）最短路

Dijkstra：快，但不能正确处理带有负权重边的图
Bellman-Ford：慢，但可以正确处理带有负权重边的图且能检测出负权环

	#define int long long
	#define INF LLONG_MAX // 不能用 LLONG_MAX 来 memset
	const int N = 1505;
	struct node
	{
	int v, w; // 点边的长度（权）
	};
	vector<node> e[N];
	int dis[N]; // 存每个点到 s 点的最短距离
	bool vis[N];
	int n, m;
	void bellmanford(int s) // 找从 s 点开始到每个点的最短距离
	{
	for (int i = 1; i <= n; i++) // 初始化
	dis[i] = INF;
	dis[s] = 0;
	bool flag; // 用来判断每一轮是否有 “松弛” 的点，没有的画算法停止
	for (int i = 1; i <= n; i++)
	{
	flag = 0;
	for (int u = 1; u <= n; u++)
	{
	if (dis[u] == INF) // 还没有被更新
	continue;
	for (auto x : e[u])
	{
	if (dis[x.v] > dis[u] + x.w)
	{
	dis[x.v] = dis[u] + x.w;
	flag = 1;
	}
	}
	}
	if (!flag)
	break;
	}
	}
	void solve()
	{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
	int u, v, w; // u 和 v 之间有长度为 w 的边
	cin >> u >> v >> w;
	e[u].push_back({v, w});
	e[v].push_back({u, w}); // 无向图时写
	}
	}

时间复杂度 $O(n*m)$

优化版（SPFA）：

	#define int long long
	#define INF LLONG_MAX
	const int N = 1505;
	struct node
	{
	int v, w; // 点边的长度（权）
	};
	vector<node> e[N];
	int dis[N], cnt[N]; // 存每个点到 s 点的最短距离
	bool vis[N];
	int n, m;
	bool spfa(int s) // Bellman-Ford 优化版
	{
	for (int i = 1; i <= n; i++) // 初始化
	dis[i] = INF, vis[i] = 0, cnt[i] = 0;
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	while (!q.empty())
	{
	auto ed = q.front();
	q.pop();
	vis[ed] = 0;
	for (auto i : e[ed])
	{
	int v = i.v, w = i.w;
	if (dis[v] > dis[ed] + w)
	{
	dis[v] = dis[ed] + w;
	cnt[v] = cnt[ed] + 1; // 记录边数
	if (cnt[v] >= n) // 存在负环
	return 1;
	if (!vis[v])
	q.push(v), vis[v] = 1;
	}
	}
	}
	return 0;
	}
	void solve()
	{

	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
	int u, v, w; // u 和 v 之间有长度为 w 的边
	cin >> u >> v >> w;
	e[u].push_back({v, w});
	e[v].push_back({u, w}); // 无向图时写
	}
	}

时间复杂度：最坏为 O（ $n*m$ ）

在遇到判断负环、存在负边时要用 SPFA

# * 全源最短路

n 次贝尔曼、n 次迪杰、Floyd（全源算法） or Johnson（全源算法）

# 4.Floyd（弗洛伊德）算法（动态规划）（全源最短路）

	const int N = 105;
	int dp[N][N], p[N][N]; // dp 来计算路径，p 来存插点
	int n;
	void floyd()
	{
	for (int k = 1; k <= n; k++)
	{
	for (int i = 1; i <= n; i++)
	{
	for (int j = 1; j <= n; j++)
	{
	if (dp[i][j] > dp[i][k] + dp[k][j])
	p[i][j] = k;
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	}
	}
	}
	}
	void path(int i, int j) // 输出最短路径
	{
	if (p[i][j] == 0)
	return;
	int k = p[i][j];
	path(i, k);
	cout << k << " ";
	path(k, j);
	}
	// 初始化
	//i != j, 无边 ->d[i][j] = INF 有边 d[i][j] = Wij
	//i = j,d[i][j] = 0;

# 5. 约翰逊（Johnson）算法（spfa 的改造可求负边权）

# 6.Tarjan 强连通分量

	struct node
	{
	int v, w;
	};
	const int N = 1010;
	vector<node> e[N];
	map<PII, int> cc;
	int dis[N];
	bool vis[N];
	int n, m;
	int dfn[N], low[N], cnt = 0, id[N], now = 0;
	stack<int> s;
	void tarjan(int u)
	{

	dfn[u] = low[u] = ++cnt;
	s.push(u);
	vis[u] = 1;
	for (auto it : e[u])
	{
	if (!dfn[it.v])
	{
	tarjan(it.v);
	low[u] = min(low[u], low[it.v]);
	}
	else if (vis[it.v])
	low[u] = min(low[u], dfn[it.v]);
	}
	if (dfn[u] == low[u])
	{
	while (1)
	{
	auto it = s.top();
	s.pop();
	id[it] = id[u];
	if (it == u)
	break;
	vis[it] = 0;
	}
	now++;
	}
	}

图论