QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409868 | #999. 边双连通分量 | Xiaohuba | WA | 0ms | 3708kb | C++23 | 3.4kb | 2024-05-12 19:54:53 | 2024-05-12 19:54:54 |
Judging History
answer
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128_t;
using uint = unsigned int;
using ull = unsigned long long;
using ulll = __uint128_t;
using db = double;
using ldb = long double;
#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define sq(x) ((x)*(x))
#define For(i,j,k) for(int i=(j); i<=(k); ++i) // NOLINT
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#define FileIO(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> il void read(T &x){ x=0;int f=1;int c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x);read(y...); }
#if __cplusplus < 201400
#warning "Please use c++14 or higher."
template<typename T> il T qpow(T x, ull y, T mod){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}
template<typename T> il constexpr T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
#else
template<typename T> il constexpr T qpow(T x, ull y, T mod){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}
template<typename T> il constexpr T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
#endif
#ifndef ONLINE_JUDGE
#define __lg log2
namespace _Debug {
template <typename T> inline void _debug(const char* format, T t) { cerr<<format<<'='<<t<<endl; }
template <class First, class... Rest> inline void _debug(const char* format, First first, Rest... rest) { while (*format != ',') cerr << *format++; cerr << '=' << first << ","; _debug(format + 1, rest...);}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& V) { os << "[ "; for (const auto& vv : V) os << vv << ", "; os << "]"; return os; }
#define debug(...) cerr<<"Line "<<__LINE__<<": ",_debug(#__VA_ARGS__, __VA_ARGS__);
};
using namespace _Debug;
#endif
// File head end
// clang-format on
namespace {
constexpr ll MAXN = 5e5 + 5;
int n, m, dfn[MAXN], low[MAXN], timer = 0, cnt = 0;
vector<int> G[MAXN], ECC[MAXN];
vector<pii> E;
stack<int> s;
void tarjan(int x, int pre) {
s.push(x);
dfn[x] = low[x] = ++timer;
for (int i : G[x]) {
int v = E[i].se;
if (!dfn[v]) {
tarjan(v, i);
if (dfn[v] == low[v]) {
int i;
++cnt;
while (!s.empty() && ((i = s.top()) >= 0)) {
s.pop();
ECC[cnt].eb(i);
if (i == v)
break;
}
}
low[x] = min(low[x], low[v]);
} else if (i != (pre ^ 1)) {
low[x] = min(low[x], dfn[v]);
}
}
}
il void solver_main() {
read(n, m);
For(i, 1, m) {
int u, v;
read(u, v);
G[u].pb(E.size()), E.eb(u, v);
G[v].pb(E.size()), E.eb(v, u);
}
For(i, 1, n) if (!dfn[i]) {
tarjan(i, -1);
if (dfn[i] == low[i]) {
++cnt;
while (!s.empty()) {
ECC[cnt].eb(s.top());
s.pop();
}
}
assert(s.empty());
}
printf("%d\n", cnt);
For(i, 1, cnt) {
cout << ECC[i].size() << ' ';
for (int j : ECC[i])
printf("%d ", j);
puts("");
}
}
}; // namespace
signed main() { return solver_main(), 0; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3708kb
input:
4 5 0 2 0 1 3 0 2 1 2 3
output:
2 4 3 2 0 1 1 4
result:
wrong answer Integer 4 violates the range [0, 3]