QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#42762#995. 桥QingyuWA 130ms23456kbC++23906b2022-08-03 17:41:022022-08-03 17:41:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-03 17:41:04]
  • 评测
  • 测评结果:WA
  • 用时:130ms
  • 内存:23456kb
  • [2022-08-03 17:41:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e5 + 50;

int n, m, dfn[N], low[N], tot, ex[N], ey[N];
int bridge[N];
vector<pair<int, int>> G[N];

void tarjan(int x, int e) {
	dfn[x] = low[x] = ++tot;
	int cnt = 0;
	for (auto [y, i] : G[x]) {
		if (!dfn[y]) {
			tarjan(y, i);
			low[x] = min(low[x], low[y]);
			if (dfn[x] < low[y]) {
				bridge[i] = true;
			}
		}
		else if (e != i) low[x] = min(low[x], dfn[y]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y;
		cin >> x >> y;
		G[x].emplace_back(y, i);
		G[y].emplace_back(x, i);
		ex[i] = x, ey[i] = y;
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			tarjan(i, i);
	for (int i = 1; i <= m; ++i) if (bridge[i])
		cout << ex[i] << ' ' << ey[i] << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 130ms
memory: 23456kb

input:

24942 387166
12556 21443
22404 16376
11073 24296
1535 11968
23745 2818
5073 12731
22550 14761
24118 12008
22695 18979
15118 13639
2080 8721
692 22578
22581 15267
9278 4127
7457 21674
17693 23448
10949 23429
9700 6009
14140 5064
7742 15164
17336 1662
18903 9760
17645 19575
6540 11942
11 4937
15282 10...

output:

16461 14146
16462 4200
16461 17395
16632 7933
16461 9707
16462 22491
16461 19413
16462 18586
16461 24247
16461 18426
16461 16814
16461 5033
16461 10924
16602 11305
16461 9218
16461 6887
16461 2630
16461 19970
16461 24516
16461 6688
16461 807
16461 10383
16461 18710
16461 5516
16461 20812
16462 13565...

result:

wrong output format Extra information in the output file