我再问tarjan scc
查看原帖
我再问tarjan scc
332549
幽灵特工楼主2021/7/13 12:56

我真是找不出哪里有错误来了,只有四十分。求各位大佬帮忙调下

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m;
int dfn[MAXN], low[MAXN], dfscnt = 0, vis[MAXN];
stack <int> S;
vector <int> G[MAXN];
vector <int> DAG[MAXN];
int w[MAXN+MAXN];//权值
int scc[MAXN], scccnt = 0;

void tarjan(int x) {
	dfn[x] = low[x] = ++dfscnt;
	S.push(x);
	vis[x] = 1;
	for (int i = 0; i < G[x].size(); i++) {
		int v = G[x][i];
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if(vis[v]) low[x] = min(low[x], low[v]);
	}
	if (dfn[x] == low[x]) {
		int tot = 0;
		while (!S.empty()) {
			vis[S.top()] = 0;
			tot += w[S.top()];
			scc[S.top()] = scccnt;
			if (S.top() == x) { S.pop(); break;}
			S.pop();
		}
		w[scccnt + MAXN] = tot;
		scccnt++;
	}
}

int indegree[MAXN];
int dp[MAXN];
int ans;
void topo() {
	queue <int> q;
	for (int i = 1; i <= scccnt; i++) {
		if (indegree[i] == 0)q.push(i);
		dp[i] = w[i + MAXN - 1];
		ans = max(ans, dp[i]);
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = 0; i < G[x].size(); i++) {
			dp[G[x][i]] = max(dp[G[x][i]], dp[x] + w[G[x][i] + MAXN - 1]);
			ans = max(ans, dp[G[x][i]]);
			indegree[G[x][i]]--;
			if (indegree[G[x][i]] == 0)q.push(G[x][i]);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> w[i];
	int x, y;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		G[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)if (!dfn[i])tarjan(i);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			if (scc[i] != scc[G[i][j]]) {
				DAG[scc[i]].push_back(scc[G[i][j]]);
				indegree[G[i][j]]++;
			}
		}
	}
	topo();
	cout << ans;
}
2021/7/13 12:56
加载中...