HDU 3313 Key Vertex（dfs + bfs）

HDU 3313 Key Vertex

題目鏈接

題意：一個有向無環圖，求s,t之間的割點

思路：先spfa找一條最短路出來，如果不存在，就n個都是割點。
然後每次從s進行dfs，找到能經過最短路上的最遠點，然後這個點就是割點，然後下次在以這個為起點dfs，不斷迭代直到找到t為止

代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100005;

int n, m, s, t, fa[N], vis[N], mark[N], d[N];
int first[N], vv[N * 3], next[N * 3], en;

const int INF = 0x3f3f3f3f;

void addedge(int a, int b) {
	vv[en] = b;
	next[en] = first[a];
	first[a] = en++;
}

bool bfs() {
	queue Q;
	for (int i = 0; i < n; i++) d[i] = INF;
	memset(vis, 0, sizeof(vis));
	Q.push(s);
	vis[s] = 1;
	d[s] = 0;
	while (!Q.empty()) {
		int u = Q.front();
		vis[u] = 0;
		Q.pop();
		for (int i = first[u]; i + 1; i = next[i]) {
			int v = vv[i];
			if (d[v] > d[u] + 1) {
				d[v] = d[u] + 1;
				fa[v] = u;
				if (!vis[v]) {
					Q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	if (d[t] >= INF) return false;
	int tmp = t;
	memset(mark, 0, sizeof(mark));
	while (tmp != s) {
		mark[tmp] = 1;
		tmp = fa[tmp];
	}
	mark[s] = mark[t] = 1;
	return true;
}

void dfs(int u) {
	for (int i = first[u]; i + 1; i = next[i]) {
		int v = vv[i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (mark[v]) {
			if (d[v] > d[s])
				s = v;
			continue;
		}
		dfs(v);
	}
}

int main() {
	while (~scanf("%d%d", &n, &m)) {
		memset(first, -1, sizeof(first));
		en = 0;
		int u, v;
		while (m--) {
			scanf("%d%d", &u, &v);
			addedge(u, v);
		}
		scanf("%d%d", &s, &t);
		if (!bfs()) {
			printf("%d\n", n);
			continue;
		}
		int ans = 1;
		memset(vis, 0, sizeof(vis));
		while (s != t) {
			dfs(s);
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}