专栏文章

scc 进阶

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopdqsn
此快照首次捕获于
2025/12/02 22:58
3 个月前
此快照最后确认于
2025/12/02 22:58
3 个月前
查看原文

HDU-2767 Proving Equivalences

题意：给定 nn 个命题和 mm 条已证蕴含关系（有向边 s1→s2s1 \to s2），求使所有命题等价（强连通）需补充的最小边数。
先缩点，然后就变成了一个 DAG。
然后要把 DAG 变成强连通，就把入度和出度为 0 的点头尾相连。
统计入度和出度，然后计算头尾，最大的就是答案。
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int t, n, m, a[N], low[N], dfn[N], col[N], tim, scc, in[N], out[N];
bool vis[N];
vector<int> nbr[N];
stack<int> stk;

void tarjan(int u) {
	vis[u] = 1;
	stk.push(u);
	dfn[u] = low[u] = ++tim;
	for (auto v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		scc++;
		while (!stk.empty()) {
			vis[stk.top()] = 0;
			col[stk.top()] = scc;
			if (stk.top() == u) {
				stk.pop();
				break;
			}
			stk.pop();
		}
	}
	return;
}

signed main() {
	for (cin >> t; t--;) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			nbr[i].clear();
		for (int i = 1; i <= m; i++) {
			int u, v;
			cin >> u >> v;
			nbr[u].push_back(v);
		}
		tim = scc = 0;
		memset (low, 0, sizeof low);
		memset (dfn, 0, sizeof dfn);
		for (int i = 1; i <= n; i++)
			if (!dfn[i])
				tarjan(i);
		for (int i = 1; i <= scc; i++) {
			in[i] = out[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			for (int v : nbr[i]) {
				if (col[i] != col[v]) {
					in[col[v]] = out[col[i]] = 1;
				}
			}
		}
		int cnt1 = 0, cnt2 = 0;
		for (int i = 1; i <= scc; i++) {
			if (!in[i])
				cnt1++;
			if (!out[i])
				cnt2++;
		}
		cout << (scc == 1 ? 0 : max(cnt1, cnt2)) << '\n';
	}
	return 0;
}

P2272 [ZJOI2007] 最大半连通子图

先缩点得到 DAG，对 DAG 求出其最长链长度与数量。
因为有重边，先去重，再拓扑 + dp。
设 dpidp_i 为到了第 ii 个连通块最长链长度，gig_i 表示数量。
当 dpv=dpu+valvdp_v = dp_u + val_v 时，gv=gv+gug_v = g_v + g_u。
否则，当 dpv<dpu+valvdp_v < dp_u + val_v 时，dpv=dpu+valvdp_v = dp_u + val_v 且 gv=gug_v = g_u。
注意取模。
CPP
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e6 + 10;

struct Edge {
	int u, v;
} edge[N]; 

int n, m, mod, ans, tim, scc, in[N], u[N], v[N], dfn[N], low[N], vis[N], val[N], dp[N], col[N], g[N];
stack<int> stk; 
vector<int> nbr[N];

void tarjan(int u) {
	vis[u] = 1;
	stk.push(u);
	dfn[u] = low[u] = ++tim;
	for (auto v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		scc++;
		while (!stk.empty()) {
			vis[stk.top()] = 0;
			col[stk.top()] = scc;
			val[scc]++;
			if (stk.top() == u) {
				stk.pop();
				break;
			}
			stk.pop();
		}
	}
	return;
}

void topo() {
	queue<int> q;
	for (int i = 1; i <= scc; i++) {
		if (!in[i])
			q.push(i), dp[i] = val[i], g[i] = 1;
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		ans = max(ans, dp[u]);
		for (int v : nbr[u]) {
			if (dp[v] == dp[u] + val[v]) {
				g[v] = (g[v] + g[u]) % mod;
			} else if (dp[v] < dp[u] + val[v]) {
				dp[v] = dp[u] + val[v];
				g[v] = g[u] % mod;
			}
			in[v]--;
			if (in[v] == 0)
				q.push(v);
		}
	}
	return;
}


bool cmp(Edge A, Edge B) {
	return A.u != B.u ? A.u < B.u : A.v < B.v;
}

signed main() {
	cin >> n >> m >> mod;
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i];
		nbr[u[i]].pb(v[i]);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i);
	}
	int num = 0;
	for (int i = 1; i <= m; i++)
		if (col[u[i]] != col[v[i]])
			edge[++num] = {col[u[i]], col[v[i]]};
	sort (edge + 1, edge + 1 + num, cmp);
	for (int i = 1; i <= n; i++)
		nbr[i].clear();
	for (int i = 1; i <= num; i++) {
		if (edge[i].u == edge[i - 1].u && edge[i].v == edge[i - 1].v) {
			continue;
		}
		nbr[edge[i].u].pb(edge[i].v);
		in[edge[i].v]++;
	}
	topo();
	cout << ans << '\n';
	int res = 0;
	for (int i = 1; i <= scc; i++) {
		if (dp[i] == ans) {
			res = (res + g[i]) % mod; 
		}
	}
	cout << res;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...