#677831 (C++14) No.1553 Lovely City

• 問題: No.1553 Lovely City
• ユーザー: rtyu
• 提出日時: 2021-07-13 14:06:17
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 166 ms / 2,000 ms
• コード長: 1,323 bytes
• コンパイル時間: 1,095 ms
• コンパイル使用メモリ: 86,772 KB
• 実行使用メモリ: 24,244 KB
• 最終ジャッジ日時: 2024-07-02 13:20:11
• 合計ジャッジ時間: 10,436 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	7 ms; 12,928 KB
testcase_01	AC	6 ms; 12,928 KB
testcase_02	AC	24 ms; 20,736 KB
testcase_03	AC	5 ms; 12,928 KB
testcase_04	AC	7 ms; 12,800 KB
testcase_05	AC	6 ms; 12,928 KB
testcase_06	AC	6 ms; 12,800 KB
testcase_07	AC	7 ms; 12,928 KB
testcase_08	AC	99 ms; 19,360 KB
testcase_09	AC	107 ms; 19,584 KB
testcase_10	AC	113 ms; 21,268 KB
testcase_11	AC	80 ms; 18,860 KB
testcase_12	AC	116 ms; 22,624 KB
testcase_13	AC	89 ms; 18,608 KB
testcase_14	AC	101 ms; 19,368 KB
testcase_15	AC	91 ms; 19,388 KB
testcase_16	AC	115 ms; 19,900 KB
testcase_17	AC	88 ms; 19,664 KB
testcase_18	AC	158 ms; 24,236 KB
testcase_19	AC	156 ms; 24,236 KB
testcase_20	AC	162 ms; 24,236 KB
testcase_21	AC	154 ms; 24,236 KB
testcase_22	AC	160 ms; 24,240 KB
testcase_23	AC	165 ms; 24,232 KB
testcase_24	AC	166 ms; 24,108 KB
testcase_25	AC	155 ms; 24,244 KB
testcase_26	AC	166 ms; 24,232 KB
testcase_27	AC	155 ms; 24,232 KB

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> v[200009];
vector<pair<int, int> > r[200009], ans;
int id[200009], ds[200009], p[200009];
queue<int> q;

int uf(int n)
{
	if (ds[n] == n) return n;
	return ds[n] = uf(ds[n]);
}

int main()
{ 
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
		ds[i] = i;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b); 
		id[b]++;
		int ua = uf(a), ub = uf(b);
		if (ua != ub) ds[ua] = ub;
	}
	for (int i = 1; i <= n; i++) 
		if (!id[i])
			q.push(i);
	int c = 0;
	while (!q.empty()) {
		int hn = q.front(); q.pop();
		c++; p[hn] = c;
		for (int i = 0; i < v[hn].size(); i++) {
			int tn = v[hn][i];
			id[tn]--;
			if (!id[tn]) q.push(tn);
		}
	}
	for (int i = 1; i <= n; i++)
		r[uf(i)].push_back(make_pair(p[i], i));
	for (int i = 1; i <= n; i++) {
		if (ds[i] != i) continue;
		sort(r[i].begin(), r[i].end());
		for (int j = 0; j + 1 < r[i].size(); j++)
			ans.push_back(make_pair(r[i][j].second, r[i][j + 1].second));
		if (!r[i][0].first)
			ans.push_back(make_pair(r[i].back().second, r[i][0].second));
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i].first << " " << ans[i].second << '\n';
	return 0;
}