QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409868#999. 边双连通分量XiaohubaWA 0ms3708kbC++233.4kb2024-05-12 19:54:532024-05-12 19:54:54

Judging History

你现在查看的是最新测评结果

  • [2024-05-12 19:54:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3708kb
  • [2024-05-12 19:54:53]
  • 提交

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]