QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127706 | #1000. 边三连通分量 | 1234567890# | WA | 4ms | 60888kb | C++14 | 4.5kb | 2023-07-19 22:30:26 | 2023-07-19 22:30:28 |
Judging History
answer
/*
灏忓簾鐗╋紝杩欓兘涓嶄細 /cf
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define mp make_pair
#define inf (ll)1e9
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
inline void write(ll x) {
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
ll n, m;
vector <pii> G[500005];
bool ban[500005];
const ll Mod = 11451411;
struct HashTable {
ll sta[500005], top;
ull to[500005];
ll head[Mod+5], num[500005], nxt[500005], tot;
inline ll val(ull x) {
ll p = x % Mod;
for(ll i = head[p]; i; i = nxt[i]) if(to[i] == x) return num[i];
return 0;
}
inline void add(ull x, ll y) {
ll p = x % Mod;
for(ll i = head[p]; i; i = nxt[i]) {
if(to[i] == x) {
num[i] += y;
return ;
}
}
num[++tot] = y, to[tot] = x, nxt[tot] = head[p], head[p] = tot;
}
inline void clear() {
tot = 0;
while(top) head[sta[top--]] = 0;
}
}H;
struct UnionSet {
ll fa[500005];
inline void makeSet(ll x) {
for(ll i = 1; i <= x; i++) fa[i] = i;
}
inline ll findSet(ll x) {
if(x == fa[x]) return x;
return fa[x] = findSet(fa[x]);
}
inline void unionSet(ll x, ll y) {
x = findSet(x), y = findSet(y);
if(x == y) return ;
fa[x] = y;
}
}U;
ll dfn[500005], low[500005], tot;
inline void Tarjan(ll x, ll fa) {
dfn[x] = low[x] = ++tot;
for(auto y : G[x]) {
if(y.se == fa) continue;
if(!dfn[y.fr]) {
Tarjan(y.fr, y.se);
if(low[y.fr] > dfn[x]) ban[y.se] = 1;
low[x] = min(low[x], low[y.fr]);
}
else low[x] = min(low[x], dfn[y.fr]);
}
}
inline void get_bri() {
for(ll i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i, 0);
}
ll seq[500005], num;
vector <pii> Tr[500005], Bk[500005];
inline void dfs(ll x, ll fa) {
dfn[x] = ++tot, seq[++num] = x;
for(auto y : G[x]) {
if(ban[y.se] || y.se == fa) continue;
if(!dfn[y.fr]) {
Tr[x].push_back(y);
dfs(y.fr, y.se);
}
else if(dfn[x] > dfn[y.fr]) Bk[x].push_back(y);
}
}
ull a[500005], b[500005];
inline void dfs2(ll x) {
for(auto y : Tr[x]) {
dfs2(y.fr);
a[y.se] = b[y.fr], b[x] ^= b[y.fr];
}
}
inline void solve() {
srand(time(NULL));
default_random_engine e(1ll * rand() * rand());
uniform_int_distribution <ull> R(0, (1ull << 63) - 1);
tot = 0;
for(ll i = 1; i <= n; i++) dfn[i] = 0;
for(ll i = 1; i <= n; i++) {
if(!dfn[i]) {
num = 0;
dfs(i, 0);
for(ll j = 1; j <= num; j++) for(auto k : Bk[seq[j]]) a[k.se] = R(e), b[seq[j]] ^= a[k.se], b[k.fr] ^= a[k.se];
dfs2(i);
H.clear();
for(ll j = 1; j <= num; j++) {
for(auto k : Bk[seq[j]]) H.add(a[k.se], 1);//, printf("! %lld\n", a[k.se]);
for(auto k : Tr[seq[j]]) H.add(a[k.se], 1);//, printf("! %lld\n", a[k.se]);
}
for(ll j = 1; j <= num; j++) {
for(auto k : Bk[seq[j]]) if(H.val(a[k.se]) > 1) ban[k.se] = 1;
for(auto k : Tr[seq[j]]) if(H.val(a[k.se]) > 1) ban[k.se] = 1;
}
// H.clear();
// for(ll j = 1; j <= num; j++) for(auto k : Bk[seq[j]]) H.add(a[k.se], 1);
// for(ll j = 1; j <= num; j++) for(auto k : Tr[seq[j]]) if(H.val(a[k.se]) >= 1) ban[k.se] = 1;
//
// H.clear();
// for(ll j = 1; j <= num; j++) for(auto k : Tr[seq[j]]) H.add(a[k.se], 1);
// for(ll j = 1; j <= num; j++) for(auto k : Bk[seq[j]]) if(H.val(a[k.se]) >= 1) ban[k.se] = 1;
}
}
}
ll cnt;
vector <ll> V[500005];
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read();
for(ll i = 1; i <= m; i++) {
ll u = read(), v = read();
G[u].push_back(mp(v, i));
G[v].push_back(mp(u, i));
}
get_bri(), solve();
U.makeSet(n);
for(ll i = 1; i <= n; i++) for(auto j : G[i]) if(i > j.fr && !ban[j.se]) U.unionSet(i, j.fr);
for(ll i = 1; i <= n; i++) V[U.findSet(i)].push_back(i), cnt += (U.findSet(i) == i);
// for(ll i = 1; i <= m; i++) printf("?? %lld %lld %lld\n", i, a[i], ban[i]);
write(cnt), putchar('\n');
for(ll i = 1; i <= n; i++) {
if(i != U.findSet(i)) continue;
for(auto j : V[i]) write(j), putchar(' ');
putchar('\n');
}
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 60888kb
input:
4 5 0 2 0 1 3 0 2 1 2 3
output:
2 3 4
result:
wrong answer Integer 4 violates the range [0, 3]