QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#588185 | #906. 强连通分量 | shiqiaqiaya | WA | 1ms | 3660kb | C++17 | 2.6kb | 2024-09-25 05:26:03 | 2024-09-25 05:26:03 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using ll = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K, class V = null_type, class C = less<>> using rb_tree = tree<K, V, C, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const ll mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);
template <ll mod = mod> ll binpow(ll a, ll b, ll res = 1) {
for (a %= mod; b; b >>= 1, (a *= a) %= mod) {
if (b & 1) (res *= a) %= mod;
}
return res;
}
template <class type = int, int len = 2> struct Tarjan_SC : vector<vector<signed>> {
vector<array<type, len>> e;
vector<signed> dfn, scc, low, vis;
vector sc = {};
Tarjan_SC(int n, int m) : vector(n), e(m), dfn(n), scc(n), low(n), vis(n) {}
void operator()(stack<signed> s = {}, int tot_dfn = 0) { // !! 会包含 0 , 可能 0 会成孤岛
for (int rt = 0; rt < size(); rt++) {
auto self = [&](auto && self, int u) -> void {
s.emplace(u), vis[u] = 1, dfn[u] = low[u] = ++tot_dfn;
for (auto & i : at(u)) {
int v = e[i][0] ^ e[i][1] ^ u;
if (!dfn[v]) self(self, v), low[u] = min(low[u], low[v]);
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) for (sc.emplace_back(); !sc.back().size() || sc.back().back() != u; s.pop()) {
scc[s.top()] = sc.size() - 1, vis[s.top()] = 0, sc.back().emplace_back(s.top());
}
};
if (!dfn[rt]) self(self, rt), s = {};
}
}
};
void QAQ() {
int n, m;
cin >> n >> m;
Tarjan_SC adj(n, m);
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
adj[u].push_back(i);
adj.e[i] = {u, v};
}
adj();
cout << adj.sc.size() << "\n";
for (auto & x : adj.sc) {
cout << x.size() << " ";
for (auto & v : x) {
cout << v << " ";
}
cout << "\n";
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1;
// cin >> t;
for (cout << fixed << setprecision(12); t--; QAQ());
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3660kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 1 2 2 4 1 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)