萌新刚学1ms oi,不输出求调
  • 板块P1656 炸铁路
  • 楼主KAqwq
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/13 16:26
  • 上次更新2024/8/13 16:37:28
查看原帖
萌新刚学1ms oi,不输出求调
448018
KAqwq楼主2024/8/13 16:26
#include <bits/stdc++.h>
#define N 100005
#define pll std::pair<LL, LL>
#define mp std::make_pair
#define ft first
#define sd second

typedef long long LL;

LL n, m;
LL head[N << 2], tail[N << 2], nxt[N << 2], tot;

inline void add_edge(LL u, LL v) {
	tail[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

pll edge[N];
std::stack<LL> s;

LL dfn[N], low[N], bel[N];
LL cnt, idx, res;

inline void dfs(LL x, LL fa) {
	low[x] = dfn[x] = ++cnt;
	s.push(x);
	for (LL i = head[x]; i; i = nxt[i]) {
		if (i != (fa ^ 1)) {
			LL ed = tail[i];
			if (!dfn[ed]) {
				dfs(ed, i);
				low[x] = std::min(low[x], low[ed]);
				if (low[ed] > dfn[x]) edge[++res] = mp(std::min(x, ed), std::max(x, ed));
			} else low[x] = std::min(low[x], dfn[ed]);
		} 
	}
	if (low[x] == dfn[x]) {
		LL v = s.top(); s.pop();
		++idx;
		while (v != x) {
			v = s.top(); s.pop();
			bel[v] = idx;
		} 
	}
}

inline LL cmp(pll x, pll y) {
	if (x.ft == y.ft) return x.sd < y.sd;
	return x.ft < y.ft;
}

int main() {
	std::cin >> n >> m;
	while (m--) {
		LL u, v;
		std::cin >> u >> v;
		add_edge(u, v); add_edge(v, u);
	}
	for (LL i = 1; i <= n; ++i) if (!dfn[i]) dfs(i, -1);
	std::sort(edge + 1, edge + 1 + res, cmp);
	for (LL i = 1; i <= res; ++i) {std::cout << edge[i].ft << ' ' << edge[i].sd << '\n';}
    return 0;
}
2024/8/13 16:26
加载中...