AcWing 398. 交通实时查询系统

大型补档计划

只有割点是必行点。

在任意一个点双中，都有分叉没有点交集的两条路径。

所以 v-DCC 缩点。

但是他问的是路径走到另一条路径的必行点。我蒙蔽了，发现自己对无向图双联通分量理解不够。因为一条边必然属于且只属于一个点双联通分量，为什么呢？因为就选这条边的两个点就构成了一个点双联通分量，所以必然存在包含的，并且由于极大性，只属于一个也显然。

缩点后变成一颗树。然后就变成了：在一颗树中，任意两点间有多少个特殊的点（割点？），用 LCA + 树上差分即可。

upd1：顺便提一句，这道题不一定保证联通，可能是森林，所以要多次dfs，但是第一次写我没多次也过了，说明数据较水。

upd2：为啥我uva WA了。

#include <cstdio>

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

const int N = 20005, M = 200005, L = 15;

int n, m, Q, num, newId[N];

int dfn[N], low[N], dfncnt, s[N], c[N], top, cnt, id[M], d[N];

bool vis[N];

int fa[N][L], dep[N];

vector<int> dcc[N], g[N];

bool cut[N];

int head[N], numE = 1;

struct E{

	int next, v;

} e[M];

void inline add(int u, int v) {

	e[++numE] = (E) { head[u], v };

	head[u] = numE;

}

void tarjan(int u, int rt) {

	dfn[u] = low[u] = ++dfncnt;

	s[++top] = u;

	if (u == rt && !head[u]) {

		dcc[++cnt].push_back(u);

		return;

	}

	int flag = 0;

	for (int i = head[u]; i; i = e[i].next) {

		int v = e[i].v;

		if (!dfn[v]) {

			tarjan(v, rt); low[u] = min(low[u], low[v]);

			if (low[v] >= dfn[u]) {

			    flag++;

    			if (u != rt || flag > 1) cut[u] = true;

    			int y; ++cnt;

    			do {

    				y = s[top--];

    				dcc[cnt].push_back(y);

    			} while (y != v);

    			dcc[cnt].push_back(u);

			}

		} else low[u] = min(low[u], dfn[v]);

	}

}

void dfs(int u) {

    vis[u] = true;

	for (int i = 1; i < L && fa[u][i - 1]; i++)

		fa[u][i] = fa[fa[u][i - 1]][i - 1];

	if (u > cnt) d[u]++;

	for (int i = 0; i < g[u].size(); i++) {

		int v = g[u][i];

		if (v == fa[u][0]) continue;

		fa[v][0] = u, dep[v] = dep[u] + 1, d[v] = d[u];

		dfs(v);

	}

}

int lca(int x, int y) {

	if (dep[x] < dep[y]) swap(x, y);

	for (int i = L - 1; ~i; i--)

		if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i];

	if (x == y) return x;

	for (int i = L - 1; ~i; i--)

		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];

	return fa[x][0];

}

int main() {

    while (scanf("%d%d", &n, &m), n || m) {

        for (int i = 1, x, y; i <= m; i++) {

    		scanf("%d%d", &x, &y);

    		add(x, y); add(y, x);

    	}

    	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i);

    	num = cnt;

    	for (int i = 1; i <= n; i++) if (cut[i]) newId[i] = ++num;

    	for (int i = 1; i <= cnt; i++) {

    		for (int j = 0; j < dcc[i].size(); j++) {

    			int x = dcc[i][j];

    			if (cut[x]){

    				g[newId[x]].push_back(i);

    				g[i].push_back(newId[x]);

    			}

    			c[x] = i;

    		}

    		for (int j = 0; j < dcc[i].size(); j++) {

    			int x = dcc[i][j];

    			for (int k = head[x]; k; k = e[k].next) {

    				int v = e[k].v;

    				if (c[v] == i) id[k >> 1] = i;

    			}

    		}

    	}

    	for (int i = 1; i <= num; i++) if (!vis[i]) dfs(i);

     	scanf("%d", &Q);

    	while (Q--) {

    		int a, b; scanf("%d%d", &a, &b);

    		a = id[a], b = id[b];

    		int p = lca(a, b);

    		printf("%d\n", d[fa[a][0]] - d[fa[p][0]] + d[fa[b][0]] - d[p]);

    	}

    	numE = 1;

    	memset(cut, false, sizeof cut);

    	memset(newId, 0, sizeof newId);

    	memset(c, 0, sizeof c);

    	memset(head, 0, sizeof head);

    	memset(dfn, 0, sizeof dfn);

    	memset(vis, false, sizeof vis);

    	memset(id, 0, sizeof id);

    	memset(fa, 0, sizeof fa);

    	for (int i = 1; i <= num; i++) g[i].clear();

    	for (int i = 1; i <= cnt; i++) dcc[i].clear();

    	dfncnt = cnt = 0;

    }

	return 0;

}

巴特西

AcWing 398. 交通实时查询系统

最新文章

热门文章