結果

問題 No.1553 Lovely City
ユーザー 👑 emthrm
提出日時 2021-06-18 21:56:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 361 ms / 2,000 ms
コード長 4,488 bytes
コンパイル時間 3,233 ms
コンパイル使用メモリ 225,704 KB
最終ジャッジ日時 2025-01-22 09:14:51
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
struct StronglyConnectedComponents {
std::vector<int> id;
std::vector<std::vector<int>> vertices, comp;
StronglyConnectedComponents(const std::vector<std::vector<int>> &graph, bool heavy = false) : graph(graph), heavy(heavy) {
n = graph.size();
rev_graph.resize(n);
for (int i = 0; i < n; ++i) for (int e : graph[i]) rev_graph[e].emplace_back(i);
used.assign(n, false);
id.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (!used[i]) dfs(i);
}
int now = 0;
for (int i = n - 1; i >= 0; --i) {
if (id[order[i]] == -1) {
if (heavy) vertices.emplace_back();
rev_dfs(order[i], now++);
}
}
comp.resize(now);
for (int i = 0; i < n; ++i) for (int e : graph[i]) {
if (id[i] != id[e]) comp[id[i]].emplace_back(id[e]);
}
// if (heavy) {
// for (int i = 0; i < now; ++i) std::sort(vertices[i].begin(), vertices[i].end());
// }
}
private:
bool heavy;
int n;
std::vector<std::vector<int>> graph, rev_graph;
std::vector<bool> used;
std::vector<int> order;
void dfs(int ver) {
used[ver] = true;
for (int e : graph[ver]) {
if (!used[e]) dfs(e);
}
order.emplace_back(ver);
}
void rev_dfs(int ver, int now) {
id[ver] = now;
if (heavy) vertices[now].emplace_back(ver);
for (int e : rev_graph[ver]) {
if (id[e] == -1) rev_dfs(e, now);
}
}
};
struct UnionFind {
UnionFind(int n) : data(n, -1) {}
int root(int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); }
bool unite(int u, int v) {
u = root(u);
v = root(v);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
return true;
}
bool same(int u, int v) { return root(u) == root(v); }
int size(int ver) { return -data[root(ver)]; }
private:
std::vector<int> data;
};
std::vector<int> topological_sort(const std::vector<std::vector<int>> &graph) {
int n = graph.size();
std::vector<int> deg(n, 0);
for (int i = 0; i < n; ++i) {
for (int e : graph[i]) ++deg[e];
}
std::queue<int> que;
for (int i = 0; i < n; ++i) {
if (deg[i] == 0) que.emplace(i);
}
std::vector<int> res;
while (!que.empty()) {
int ver = que.front(); que.pop();
res.emplace_back(ver);
for (int e : graph[ver]) {
if (--deg[e] == 0) que.emplace(e);
}
}
return res.size() == n ? res : std::vector<int>();
}
int main() {
int n, m; cin >> n >> m;
vector<vector<int>> graph(n);
while (m--) {
int u, v; cin >> u >> v; --u; --v;
graph[u].emplace_back(v);
}
StronglyConnectedComponents scc(graph, true);
const int x = scc.comp.size();
UnionFind uf(x);
REP(i, x) for (int e : scc.comp[i]) uf.unite(i, e);
map<int, vector<int>> root;
REP(i, x) root[uf.root(i)].emplace_back(i);
vector<int> ts = topological_sort(scc.comp);
assert(!ts.empty());
vector<int> inv(x, -1);
REP(i, x) inv[ts[i]] = i;
vector<int> a, b;
for (auto [_, v] : root) {
sort(ALL(v), [&](int l, int r) -> bool { return inv[l] < inv[r]; });
int last = -1;
bool need_loop = false;
for (int e : v) {
for (int ver : scc.vertices[e]) {
if (last != -1) {
a.emplace_back(last);
b.emplace_back(ver);
}
last = ver;
}
need_loop |= scc.vertices[e].size() > 1;
}
if (need_loop) {
a.emplace_back(last);
b.emplace_back(scc.vertices[v.front()].front());
}
}
int k = a.size();
cout << k << '\n';
REP(i, k) cout << a[i] + 1 << ' ' << b[i] + 1 << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0