高等图论

• Tarjan算法求强连通分量
• $x$ 是正在搜索的节点。看看它是否在强连通分量之中。情况1：存在后向边，指向祖先节点；情况2：存在横叉边，横叉边再走到祖先节点。
• 时间戳：对于每个点，定义两个时间戳。$dfn[u]$ 表示遍历到u的时间戳；$low[u]$ 表示从 $u$ 开始走，所能遍历到的最小时间戳。$u$ 是其所在强连通分量的最高点等价于 $dfn[u]=low[u]$.
• 最后连通分量编号逆序一定是拓扑序，所以其实不用进行拓扑排序。
• 题意：找到一个图中所有满足这样关系的节点的数量：从图中其他任何节点都可以到达这个节点。
• 对于这道题，如果不是拓扑图，需要每一个点都 $bfs$ 一遍，复杂度 $O(n^2)$，太高。但是如果是拓扑图的话，如果存在至少两个出度为 $0$ 的点，那么这两个点相互无法到达，答案就是 $0$。但是，如果只有一个出度为 $0$ 的点，那么答案就是出度为 $0$ 的这个连通块的大小。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 10010, maxm = 50010;
int h[maxn], e[maxm], ne[maxm], idx;
int N, M, dfn[maxn], low[maxn];
int id[maxn], sz[maxn], out[maxn], timestamp, scc_cnt;
bool in_stk[maxn];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
stack<int> stk;

void tarjan(int u) {
//千万别写成 timestamp++ !!!
	dfn[u] = low[u] = ++timestamp;
	stk.push(u), in_stk[u] = true;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		scc_cnt++;
		int v;
		do {
			v = stk.top(); stk.pop();
			in_stk[v] = false;
			id[v] = scc_cnt;
			sz[scc_cnt]++;
		} while (v != u);
	}
}
void solve() {
	for (int i = 1; i <= N; i++) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	for (int u = 1; u <= N; u++) {
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			int a = id[u], b = id[v];
			if (a != b) out[a]++;
		}
	}
	int zero = 0, sum = 0;
	for (int i = 1; i <= scc_cnt; i++) {
		if (!out[i]) {
			zero++;
			sum += sz[i];
			if (zero > 1) {
				sum = 0;
				break;
			}
		}
	}
	printf("%d\n", sum);
}
int main() {
	scanf("%d%d", &N, &M);
	memset(h, -1, sizeof h);
	for (int i = 0; i < M; i++) 
    {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
	}
	solve();
	return 0;
}

• 边双连通分量算法
• 给一个无向连通图，问至少加几条边，可以把这个图变成边双连通分量。
• 求桥：dfn[u] < low[v]
• 一个图是边双连通分量，等价于任意两点之间有至少两条相互分离的路径（即两条路径没有一条重合的道路）。
• 双连通分量内任何两点间都是至少有两条相互分离的路径，因此缩点之后，变成了一个树。设图中度数为1的节点有cnt个，那么最后要加的边是 (cnt + 1) / 2 个。其实就是把叶节点两两相连（如果cnt是奇数就把多余的叶节点随便连一下）。这样，就变成了一个双连通图。

#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int maxn = 5010, maxm = 20010;
int h[maxn], ne[maxm], e[maxm], idx;
int id[maxn], low[maxn], dfn[maxn], timestamp, dcc_cnt;
int N, M, d[maxn];
bool is_bridge[maxm];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
stack<int> stk;
// from 记载从哪条边来的。
void tarjan(int u, int from) {
	low[u] = dfn[u] = ++timestamp;
	stk.push(u);
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			
			//dfn[u] < low[v] 等价于 u 与 v 之间的边是桥。
			if (dfn[u] < low[v]) {
				//双向边的编号是两两成对的。
				is_bridge[i] = is_bridge[i ^ 1] = true;
			}
		}
		
		else if (i != (from ^ 1)) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		++dcc_cnt;
		int v;
		do {
			v = stk.top(); stk.pop();
			id[v] = dcc_cnt;
		} while (v != u);
	}
}
int main() {
	scanf("%d%d", &N, &M);
	memset(h, -1, sizeof h);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	tarjan(1, -1);
	for (int i = 0; i < idx; i++) {
		if (is_bridge[i]) d[id[e[i]]]++;
	}
	int cnt = 0;
	for (int i = 1; i <= dcc_cnt; i++) {
		if (d[i] == 1) cnt++;
	}
	printf("%d\n", (cnt + 1) / 2);
	return 0;
}

• 点双连通分量算法
• 删除图中的一个点之后，连通块最多有多少。
• 求割点：（1）当u不是根节点时，$low(v)>=dfn(u)$，则u是割点；当u是根节点时，至少有两个子节点 $y_i$，有 $low(y_i)>=dfn(u)$
• 统计原本的连通块儿数量blocks，以及枚举每个连通块儿删掉一个点可以得到的最大的连通块儿数量res，答案就是blocks + res - 1.

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10010, maxm = 30010;
int h[maxn], e[maxm], ne[maxm], idx;
int N, M, res, blocks, root;
int dfn[maxn], low[maxn], timestamp;
void tarjan(int u) {
	dfn[u] = low[u] = ++timestamp;
	int cnt = 0;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) cnt++;
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if (u != root) cnt++;
	res = max(res, cnt);
}
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main() {
	while (scanf("%d%d", &N, &M) && N) {
		memset(dfn, 0, sizeof dfn);
		memset(h, -1, sizeof h);
		timestamp = idx = 0;
		for (int i = 0; i < M; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b), add(b, a);
		}
		res = blocks = 0;
		for (root = 0; root < N; root++) {
			if (!dfn[root]) {
				blocks++;
				tarjan(root);
			}
		}
		printf("%d\n", blocks + res - 1);
	}
	return 0;
}

• 题意：对于一个无向图，在图中找到一些点集{S}，使得不管取下图中哪一个点，其他点都可以到达{S}中的至少一个点。求问点集大小最小是多少，以及在此条件下的方案总数。
• 点集大小至少为2；
• 情况1. 若无割点，不管哪下那个点，图都是连通的，那么点集大小为2；
• 情况2：有割点的话需要缩点，每个割点单独作为一个点，从每个 v-DCC 向其包含的每个割点连一条边。若v-DCC度数为1，那么需要在改分量非割点的地方设置一个出口；若度数大于1，则无需设置出口。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
typedef unsigned long long ll;
const int maxn = 1010, maxm = 1010;
int h[maxn], e[maxm], ne[maxm], idx;
int dfn[maxn], low[maxn], dcc_cnt, timestamp;
int N, M, root, kase;
bool is_cut[maxn];
vector<int> dcc[maxn];  //这个存的是每一个连通分量含哪些节点。
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
stack<int> stk;
void tarjan(int u) {
	dfn[u] = low[u] = ++timestamp;
	stk.push(u);
	if (u == root && h[u] == -1) {
		dcc_cnt++;
		dcc[dcc_cnt].push_back(u);
		return;
	}
	int cnt = 0;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (dfn[u] <= low[v]) {
				cnt++;
				if (u != root || cnt > 1) is_cut[u] = true;
				dcc_cnt++;
				int y;
				do {
					y = stk.top(); stk.pop();
					dcc[dcc_cnt].push_back(y);
				} while (y != v);
				dcc[dcc_cnt].push_back(u);
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
}
int main() {
	while (scanf("%d", &M) && M) {
		for (int i = 1; i <= dcc_cnt; i++) dcc[i].clear();
		memset(h, -1, sizeof h);
		memset(dfn, 0, sizeof dfn);
		memset(is_cut, 0, sizeof is_cut);
		while (stk.size()) stk.pop();
		idx = N = dcc_cnt = timestamp = 0;
		for (int i = 0; i < M; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b), add(b, a);
			N = max(a, N), N = max(b, N);
		}
		for (root = 1; root <= N; root++) {
			if (!dfn[root]) tarjan(root);
		}
		ll num = 1;
		int res = 0;
		for (int i = 1; i <= dcc_cnt; i++) {
			int cnt = 0, sz = dcc[i].size();
			for (int j = 0; j < sz; j++) {
				if (is_cut[dcc[i][j]]) cnt++;
			}
			
			if (cnt == 0) {
				if (sz > 1) res += 2, num *= (sz - 1) * sz / 2;
				else res++;
				
			}
			else if (cnt == 1) res++, num *= sz - 1;
		}
		printf("Case %d: %d %llu\n", ++kase, res, num); 
	}
	return 0;
}

• 所有的边都是双向边，而且要看成两条边，因此所有点入读与出度相等，其实就是欧拉回路。就算铲雪车停在一条路的中间，总时间是不会变的。因此只需要算一下所有路长度的两倍就行。
• 输出的话，格式有要求，要求分钟四舍五入、两位、保留前导零，可以这么做：printf("%.f:%02.f\n", hours, minutes);

• 给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。输入：第一行包含一个整数 $t$， t ∈ { 1 , 2 } t \in \lbrace 1,2 \rbrace t∈{1,2}，如果 $t=1$，表示所给图为无向图，如果 $t=2$，表示所给图为有向图。第二行包含两个整数 $n,m$，表示图的结点数和边数。接下来 $m$ 行中，第 $i$ 行两个整数 $v_i,u_i$，表示第 $i$ 条边（从 $1$ 开始编号）。如果 $t=1$ 则表示 $v_i$ 到 $u_i$ 有一条无向边。如果 $t=2$ 则表示 $v_i$ 到 $u_i$ 有一条有向边。图中可能有重边也可能有自环。
• 复杂度是$O(m)$.
• 复原欧拉回路边的编号

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100010, maxm = 400010;
int h[maxn], e[maxm], ne[maxm], idx;
bool used[maxm];
int N, M, ans[maxm / 2], cnt, type, din[maxn], dout[maxn];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
	//引用千万不要忘！用引用的目的其实是为了针对自环特别多的情况，可以把父结点的那条边也删掉。
	for (int& i = h[u]; i != -1;) {
		if (used[i]) {
			h[u] = ne[i];  ///注意这个删除节点的操作还是很简洁的！
			continue;
		}
		/*
		这个used[i] = true 必须要带上。因为尽管看似这条边已经删掉了，但是只是对于子节点
		而言。而对于父结点还没有删掉。
		*/
		used[i] = true;
		if (type == 1) used[i ^ 1] = true;
		int t;
		if (type == 1) {
			t = i / 2 + 1;
			if (i & 1) t = -t;
		}
		else t = i + 1;
		int v = e[i];
		i = ne[i];
		dfs(v);
		ans[cnt++] = t;
	}
}
int main() {
	scanf("%d%d%d", &type, &N, &M);
	memset(h, -1, sizeof h);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
		if (type == 1) add(b, a);
		dout[a]++, din[b]++;
	}
	if (type == 1) {
		for (int i = 1; i <= N; i++) {
			if (din[i] + dout[i] & 1) {
				printf("NO\n");
				return 0;
			}
		}
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (din[i] != dout[i]) {
				printf("NO\n");
				return 0;
			}
		}
	}
	//要从至少有一条边节点开始搜索
	for (int i = 1; i <= N; i++) {
		if (h[i] != -1) {
			dfs(i);
			break;
		}
	}
	//cnt < M 意味着图中的边不连通。
	if (cnt < M) {
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	for (int i = cnt - 1; i >= 0; i--) printf("%d%c", ans[i], i == 0 ? '\n' : ' ');
	return 0;
}

• 输出一个 DAG 的拓扑序

#include<iostream>
#include<queue>
#include<cstring>
const int maxn = 110, maxm = 5010;
using namespace std;
int h[maxn], e[maxm], ne[maxm], idx;
int N, ans[maxn], din[maxn], cnt;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void toposort() {
	queue<int> que;
	//首先，把所有入度为0的点加入队列。
	for (int i = 1; i <= N; i++) {
		if (!din[i]) {
			ans[++cnt] = i;
			que.push(i);
		}
	}
	while (que.size()) {
		int u = que.front(); que.pop();
		//接着，每遍历一条u指出的边，就把u指向的顶点的入度减1。直到v的入度为0时再把v加进队列。
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			din[v]--;
			if (!din[v]) que.push(v), ans[++cnt] = v;
		}
	}
	//若题目数据不能保证一定有解，则最后需要判断cnt == N（总共加进去了N个点）,是的话就存在拓扑序，否则就不存在。
}
int main() {
	scanf("%d", &N);
	memset(h, -1, sizeof h);
	for (int i = 1; i <= N; i++) {
		int t;
		while (cin >> t, t) add(i, t), din[t]++;
	}
	toposort();
	for (int i = 1; i <= cnt; i++) printf("%d%c", ans[i], i == cnt ? '\n' : ' ');
	return 0;
}

• 关于差分约束的问题：

1. 若边权任意，则需要用spfa判断环，跑最短路或最长路；
2. 若边权非负，可以用tarjan算法
3. 若边权均正，那么可以用拓扑排序跑一遍最长路即可。
   但是还是要掌握下面的，已知拓扑序怎样求最长路。

• 这道题也让我们明白为什么求最小值要求最长路。而且这道题边不要连反。

• 给定一张 $N$ 个点 $M$ 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。$1\le N,M\le 30000$
• 用一个 $01$ 的二进制串可以很好的表示哪些点可以到这个点。
• 用 $bitset$ 代替 $bool$ 数组，可以把时间减少到 $1/32$，因为 $bitset$ 的位数比较少，按位或运算比较快。
• 这个我是建了反向图，然后宽搜（用到了拓扑排序）。