結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-20 21:49:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 262 ms / 2,000 ms |
コード長 | 2,009 bytes |
コンパイル時間 | 1,954 ms |
コンパイル使用メモリ | 178,304 KB |
実行使用メモリ | 40,112 KB |
最終ジャッジ日時 | 2024-06-22 22:38:55 |
合計ジャッジ時間 | 10,610 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i, a, n) for(int i=(a); i<(n); ++i)#define per(i, a, n) for(int i=(a); i>(n); --i)#define pb emplace_back#define mp make_pair#define clr(a, b) memset(a, b, sizeof(a))#define all(x) (x).begin(),(x).end()#define lowbit(x) (x & -x)#define fi first#define se second#define lson o<<1#define rson o<<1|1#define gmid l[o]+r[o]>>1using LL = long long;using ULL = unsigned long long;using pii = pair<int,int>;using PLL = pair<LL, LL>;using UI = unsigned int;const int mod = 1e9 + 7;const int inf = 0x3f3f3f3f;const double EPS = 1e-8;const double PI = acos(-1.0);const int N = 2e5 + 10;vector<int> V[N], G[N], A[N], P[N];vector<pii> ans;int n, m, deg[N], idx[N];int com, sz[N];void bfs(int x){queue<int> Q;Q.emplace(x);idx[x] = ++com;sz[com] = 0;while(!Q.empty()){x = Q.front(); Q.pop();P[com].pb(x);++sz[com];for(int j : G[x]){if(!idx[j]){idx[j] = com;Q.emplace(j);}}}}int main(){scanf("%d %d", &n, &m);int x, y;clr(deg, 0);while(m--){scanf("%d %d", &x, &y);V[x].pb(y);++deg[y];G[x].pb(y);G[y].pb(x);}clr(idx, 0);com = 0;rep(i, 1, n + 1){if(!idx[i]){bfs(i);}}queue<int> Q;rep(i, 1, n + 1){if(deg[i] == 0){Q.emplace(i);}}while(!Q.empty()){x = Q.front(); Q.pop();--sz[idx[x]];A[idx[x]].pb(x);for(int j : V[x]){if(--deg[j] == 0){Q.emplace(j);}}}rep(i, 1, com + 1){if(sz[i] == 0){rep(j, 1, A[i].size()){ans.pb(A[i][j-1], A[i][j]);}} else {rep(j, 1, P[i].size()){ans.pb(P[i][j-1], P[i][j]);}ans.pb(P[i].back(), P[i][0]);}}printf("%d\n", (int)ans.size());for(pii p : ans) printf("%d %d\n", p.fi, p.se);return 0;}