Atcoder arc143

發表於 更新於 分類於 ， Disqus： 文章字數： 711 所需閱讀時間 ≈ 2 分鐘
D(dfs,无向图无桥联通块,强连通分量)

哎 超时8min过了E,但这个D我还是不会

D

评分2229

题目

https://atcoder.jp/contests/arc143/tasks/arc143_d

左边1-n的点

右边1-n的点

左i-右i有边

给你m对数 (ai,bi), 你需要输出长度为m的0/1字符串

如果你要(左ai-右bi) 则第i个字符为0, 如果你要(左bi-右ai)则第i个字符是1

最终让图里的桥最少, 求一个字符串方案

范围

n 2e5

m 2e5

2s

1024mb

题解

我的思路

只想着贪心

首先如果一个边在任意环里那它就不是桥, 所以希望能贪心尽量让边进入环

统计给的m对数中, 每个值出现的次数

对于只出现一次的无药可救,先不管它

对于出现2次的,那就安排让它左右各连出一个

如果运算过程中某个点一侧被连了,另一侧没有连,还有关于这个点的数对,那么就去连另一测

已经两侧都连了的就不管

但就写的来看似乎有问题, 还蛮多人过了这个题

题解

一句话 把它当成一个未定向的有向图， 然后在图上找环， 并定向即可

首先考虑一个n个点, m边的无向图, 按照ai-bi的连接

如果有边在无向图中也是桥, 那么在题目问题中它只能是桥

对于无向图来说,移除了所有桥以后, 每个连通块可以单独独立处理

所以假设 拿到一个无向连通 无桥图

总有办法给所有边一个方向,让连通图变成强联通图

一个办法就是 直接做dfs树

代码

https://atcoder.jp/contests/arc143/submissions/32806181

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
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back

int read(){int r;scanf("%intd",&r);return r;} // read
int n;
int m;

char s[200010]; // answer
pair<int,int> ab[200010];
vector<array<int,3>> u2[200010]; // {v, ab idx, '0','1'}
bool vis[200010];

void dfs(int u){
  vis[u] = true;
  for(auto [v,i,o]:u2[u]){
    if(s[i]) continue; // 边处理过
    s[i] = (char)o;
    if(!vis[v]) dfs(v);
  }
}


int main(){
  n = read();
  m = read();
  rep(i,0,m) ab[i].first = read();
  rep(i,0,m){
    int a = ab[i].first;
    int b = ab[i].second = read();
    u2[a].pb({b,i,(int)'0'});
    u2[b].pb({a,i,(int)'1'});
  }
  rep(i,1,n+1){
    if(vis[i])continue;
    dfs(i);
  }
  rep(i,0,m){
    if(!s[i]) s[i] = '0';
  }
  printf("%s\n",s);
  return 0;
}

总结

D

知道逻辑以后 10min 随便写了QAQ

我不知道应该怎么归类,信息提取,还是有向图无向图连通性质

我觉得有一点 算是 无向图的无桥联通块 能通过指定所有边 变成有向图的强连通分量这一点吧,但好像又是一个提炼性质

哎

参考

官方题解