結果
問題 | No.1553 Lovely City |
ユーザー |
|
提出日時 | 2021-07-02 19:19:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 780 ms / 2,000 ms |
コード長 | 2,963 bytes |
コンパイル時間 | 2,800 ms |
コンパイル使用メモリ | 213,456 KB |
最終ジャッジ日時 | 2025-01-22 15:34:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#define _USE_MATH_DEFINES#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define MT make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define RT returnusing ll = long long;using pii = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;vector<int> topologicalSort(const vector<vector<int> > &graph) {int V = (int)graph.size(), cur = 0;vector<int> deg(V), res(V);stack<int> stk;for (int i = 0; i < V; ++i)for (int v : graph[i])deg[v]++;for (int i = 0; i < V; ++i)if (deg[i] == 0)stk.push(i);while (!stk.empty()) {int v = stk.top(); stk.pop();res[cur++] = v;for (int w : graph[v])if (!--deg[w])stk.push(w);}return cur == V ? res : vector<int>();}class ConnectedComponents {public:vector<vector<int>> operator()(const vector<vi>& G) {int n = (int)G.size();visited = vector<int>(n);for (int i = 0; i < n; ++i) {if (!visited[i]) {result.push_back(vector<int>());dfs(G, i, -1);}}return result;}private:vector<int> visited;vector<vector<int>> result;void dfs(const vector<vi>& G, int vertex, int prev) {if (visited[vertex]++) return;result.back().push_back(vertex);for (auto edge : G[vertex]) {int to = edge;if (to != prev) {dfs(G, to, prev);}}}};void solve() {int N, M;cin >> N >> M;vector<vi> G(N), H(N);vi U(M), V(M);rep(i, M) {cin >> U[i] >> V[i];--U[i];--V[i];G[U[i]].push_back(V[i]);H[U[i]].push_back(V[i]);H[V[i]].push_back(U[i]);}// weakly connected componentsauto CC = ConnectedComponents()(H);vector<pii> ans;vi A(N, -1); // 頂点番号を振り直すeach(C, CC) {int n = sz(C);rep(i, n) {A[C[i]] = i;}vector<vi> Z(n);each(u, C) each(v, G[u]) {Z[A[u]].push_back(A[v]);}auto TS = topologicalSort(Z);if (TS.empty()) {rep(i, n) {ans.emplace_back(C[i], C[(i + 1) % n]);}} else {rep(i, n - 1) {ans.emplace_back(C[TS[i]], C[TS[(i + 1) % n]]);}}}cout << sz(ans) << endl;each(a, ans) {cout << a.first + 1 << ' ' << a.second + 1 << endl;}}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);solve();return 0;}