Atcoder abc334

發表於 更新於 分類於 ， Disqus： 文章字數： 685 所需閱讀時間 ≈ 2 分鐘
G(双连通分量)

https://atcoder.jp/contests/abc334

G - Christmas Color Grid 2

h x w 地图上0/1

4邻的1为连通块

求等概率把一个1改成0以后 exp(连通块个数) mod 998244353

h,w 1000

2s

1024mb

我的思路

就是找 去掉点后是否还连通，tarjan的算法

然后写出问题了

题解

一样的，但是tarjan我的 做并查集有问题

因为

1
2
3
4
5
a-b
 \|
  c
  |\
  d-e

这样的话 a-c 有两条连通，c-d有两条连通，但是a-d只有会有关键节点c

1
2
3
4
3 3  
##.  
###  
.##

所以 应该是 每个点是割点时，向下的low >= n时, 会生成

代码

https://atcoder.jp/contests/abc334/submissions/50072514

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
int read(){int r;scanf("%d",&r);return r;}
const int N=1010,M=1000010;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
int h,w;
int dfn[N][N],low[N][N];
int f[N][N]; // 相连的 点-双连通分量 数量 -1
int cnt[M]; // 单连通块[b]大小
int bl[N][N]; // bl[x][y] = 单连通块id
char s[N][N];
void tarjan(int x,int y,int fx,int fy,int b,int dep=1){
  low[x][y]=dfn[x][y]=dep; // 有向图 ++tick;, 无向图可以直接dep
  cnt[bl[x][y]=b]++;
  rep(i,0,4) {
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx<1||nx>h||ny<1||ny>w||s[nx][ny]=='.') continue;
    if(!dfn[nx][ny]){
      tarjan(nx,ny,x,y,b,dep+1);
      low[x][y]=min(low[x][y],low[nx][ny]);
      if(low[nx][ny]>=dfn[x][y]) f[x][y]++;
    }else if(nx != fx or ny != fy){ // 非回边
      low[x][y]=min(low[x][y],dfn[nx][ny]); // 这里不是low 是dfn, 同样是8字形的问题
    }
  }
  if(x==fx and y==fy) f[x][y]--; // root
}
int main(){
  h=read();
  w=read();
  rep(i,1,h+1) scanf("%s",s[i]+1);
  int t=0;
  rep(i,1,h+1) rep(j,1,w+1) if(s[i][j]=='#' && !dfn[i][j]) tarjan(i,j,i,j,++t);
  mint a1=0;
  mint a2=0;
  rep(i,1,h+1) rep(j,1,w+1) if(s[i][j]=='#'){
    a1 ++;
    a2 += (cnt[bl[i][j]]==1)?-1:f[i][j];
  }
  printf("%d\n",(a2*a1.pow(MOD-2)+t).val()); // a1可能为0 不要inv()
  return 0;
}

总结

点-双连通： 任意两点之间至少存在两条“点不重复”的路径，即内部无割点。

我的问题在于 tarjan的细节还是有问题，而这里并不能像有向图的强连通分量那样做 并查集

因为

1
2
3
4
5
a-b
 \|
  c
  |\
  d-e

这样的话 a-c 有两条连通，c-d有两条连通，但是a-d只有会有关键节点c

所以这里是{a,b,c},{c,d,e},

如果要求的话，同样的tarjan(u), 但是边(u->v)在dfs时入栈，然后当有割点(low[v] >= dfn[u])时,把栈顶直到(u->v)的全部边 作为一个集合构成 点-双连通