割边模板 过不了样例但 80
  • 板块P1656 炸铁路
  • 楼主hjqhs
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/4 21:32
  • 上次更新2024/8/4 23:08:40
查看原帖
割边模板 过不了样例但 80
724988
hjqhs楼主2024/8/4 21:32
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
typedef long long ll;
typedef unsigned long long ull;
const int N = 1005;
const int M = 5005;
const int INF = 0x3f3f3f3f;
int n, m, ecnt, dfstime, h[N], dfn[N], low[N], fa[N];
vector<pair<int, int> > bri;
struct edge {
	int to, nxt;
} e[M];
void add_edge(int u,int v) {
	++ ecnt;
	e[ecnt].nxt = h[u];
	h[u] = ecnt;
	e[ecnt].to = v;	
}
void tarjan(int u) {
  low[u] = dfn[u] = ++ dfstime;
  for(int i = h[u]; i; i = e[i].nxt) {
  	int v = e[i].to;
  	if(fa[u] != v) {
  		fa[v] = u;
  		if(!dfn[v]) {
  			fa[v] = u;
  			tarjan(v);
  			low[u] = min(low[u], low[v]);
  			if(dfn[u] < low[v]) bri.emplace_back(make_pair(min(u, v), max(u, v)));
  		} else low[u] = min(low[u], dfn[v]);
  	}
  }
}
void solve() {
	cin >> n >> m;
	rep(i, 1, m) {
		int u, v; cin >> u >> v;
		add_edge(u, v), add_edge(v, u);
	}
	rep(i, 1, n) if(!dfn[i]) tarjan(i);
	sort(bri.begin(), bri.end());
	for(int i = 0; i < bri.size(); ++ i) {
		cout << bri[i].first << ' ' << bri[i].second << '\n';
	}
	return;
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	// cin >> T;
	while(T --) solve();
	return 0;
}
2024/8/4 21:32
加载中...