tarjan求助
  • 板块灌水区
  • 楼主syr1125
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/4/18 15:17
  • 上次更新2024/4/18 19:23:07
查看原帖
tarjan求助
561949
syr1125楼主2024/4/18 15:17

rt,写了一份缩点代码,有问题 注:没有输出,就是纯缩点,也不是缩点模板题的代码。

#include <bits/stdc++.h>
using namespace std;

int n, m, t = 0, cnt = 0;
int point[10005];
vector<int> e[10005], a[10005];
int dfn[10005], low[10005], id[10005];
stack<int> st;
int vis[10005];

void tarjan(int now)
{
	if (dfn[now]) return;
	st.push(now), vis[now] = 1;
	dfn[now] = low[now] = ++ t;
	for (int i = 0; i < e[now].size(); i ++)
	{
		if (dfn[e[now][i]] == 0)
		{
			tarjan(e[now][i]);
			low[now] = min(low[now], low[e[now][i]]);
		}
		else if (vis[e[now][i]])
		{
			low[now] = min(low[now], low[e[now][i]]);
		}
	}
	if (dfn[now] == low[now])
	{
		cnt ++;
		while (!st.empty())
		{
			int cur = st.top();
			st.pop(); 
			vis[cur] = 0, id[cur] = cnt;
			if (cur == now) break;
			point[now] += point[cur];
		}
	}
}

void init()
{
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 0; j < e[i].size(); j ++)
		{
			if (id[e[i][j]] != id[i])
			{
				a[id[i]].push_back(id[e[i][j]]);
			}
		}
	}
} 

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", &point[i]);
	}
	for (int i = 1; i <= m; i ++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		e[x].push_back(y);
	}
	tarjan(1);
	init();
	return 0;
}

2024/4/18 15:17
加载中...