刚学的tarjan割边算法有不解
  • 板块P1656 炸铁路
  • 楼主Wh1t3zZlo
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/10/1 14:00
  • 上次更新2024/10/1 16:29:12
查看原帖
刚学的tarjan割边算法有不解
1232566
Wh1t3zZlo楼主2024/10/1 14:00
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct edge
{
	int x, y;
};

vector<int>e;
vector<int>head[5005];

vector<edge>bri;

int n, m,dfs[205],low[205],cnt;

void add(int u,int v)
{
	e.push_back(v);
	head[u].push_back(e.size() - 1);
}

void Tarjan(int u, int in_edge)
{
	dfs[u] = ++cnt; low[u] = cnt;
	for (int i = 0; i < head[u].size(); i++)
	{
		int j = head[u][i], v = e[j];
		if (!dfs[v])
		{
			Tarjan(v, j);
			low[u] = min(low[u], low[v]);
			if (low[v] > dfs[u])
			{
				if (u < v)
					bri.push_back(edge{ u,v });
				else
					bri.push_back(edge{ v,u });
			}
		}
		else if ((in_edge ^1 ) != j)
		{
			low[u] = min(low[u], dfs[v]);
		}
	}

}

bool cmp(edge x, edge y)
{
	if (x.x == y.x) return x.y < y.y;
	else return x.x < y.x;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		add(u, v); add(v, u);
	}

	Tarjan(1, 0);

	sort(bri.begin(), bri.end(), cmp);
	for (edge x : bri)
	{
		cout << x.x << " " << x.y << endl;
	}

	return 0;
}

这是ac代码,else if ((in_edge ^1 ) != j),这段话是判断反边,因为是add(u,v)后面马上跟了个add(v,u)所以按道理来说反边应该是和正向边的编号+1是一样的,所以如果(in_edge ^1 ) != j那j就不是反边,但是为什么不能用(in_edge +1 ) != j来判断j是不是反边呢,因为反边不就是正向边编号+1吗,改了之后会wa三个点,求解

2024/10/1 14:00
加载中...