110 選手班 - 進階圖論

連通性

討論無向圖上的連通性
邊雙連通：在一張連通無向途中，若點\(u\)和點\(v\)無法透過刪除任何一條邊，使他們不連通，則稱\(u\)和\(v\)點雙連通
點雙連通：在一張連通無向途中，若點\(u\)和點\(v\)無法透過刪除任何一個點，使他們不連通，則稱\(u\)和\(v\)點雙連通

邊雙連通

傳遞性：若\(x\)和\(y\)邊雙連通，\(y\)和\(z\)邊雙連通，則\(x\)和\(z\)邊雙連通
判斷一張圖是否邊雙連通：移除每條邊\(e\)，檢查是否整張圖還連通。

橋

bridge / cut edge
割邊
定義：若移除邊\(e\)會使得圖不連通，則稱\(e\)為橋

Problem

給定一張圖\(G\)，請找出圖中的所有橋(Bridge)

Tarjan

不少他發明的算法都以他的名字命名，以至於有時會讓人混淆幾種不同的算法。 –wiki

DFS Tree

Back Edge: 一定不是橋
Tree Edge: 有可能是橋
- 刪除後要透過back edge連通
- 邊\((u,v)\)往上連到祖先
  - \(v\)有back edge
  - \(v\)的子孫有back edge且高度只少連到\(u\)

Low Function

\(\text{low}(v):=\)對於無向圖上的節點 \(v\)，\(\text{low}(v)\)被定義為「在不透過父邊的情況下，能夠到達深度最淺的祖先的深度」

	a	b	c	d	e	f	g	h
dep	0	1	2	3	4	2	3	2
low	0	0	1	1	2	2	3	0

\(\text{low}(v) = \text{dep}(v)\rightarrow v\)的父邊是橋
無法不透過父邊到達更淺的祖先

Find \(\text{low}\)

DFS 時從 \(v\) 透過邊 \(e\) 走到 \(u\)：
\(u\)還沒拜訪過：
- \(e\)是樹邊，有機會從 \(u\) 或他的小孩經過回邊走到更淺的祖先
- 對 \(u\) 做DFS後，將 \(\text{low}(v)\) 和 \(\text{low}(u)\) 取 \(\min\)
\(u\)拜訪過：
- \(e\)是回邊，根據定義可以更新\(\text{low}(v)\)
- 將 \(\text{low}(v)\) 和 \(\text{dep}(u)\) 取 \(\min\)

Time Complexity

DFS: \(\mathcal{O}(V + E)\)

 const int N = 100010 ;
vector<int> g[N];
bool vis[N], bridge[N] ;
int low[N], dep[N] ;
 
void dfs(int x) {
    vis[x] = true ;
    low[x] = dep[x] ;
    for(auto i:g[x]) {
        if(vis[i]) {
            low[x] = min(low[x], dep[i]) ;
        } else {
            dep[i] = dep[x] + 1 ;
            dfs(i) ;
            low[x] = min(low[x], low[i]) ;
        }
    }
    if(low[x] == dep[x]) bridge[x] = true ;
}

邊雙連通分量

Bridge-connected Components
BCC
定義：圖上「邊雙連通」的連通子圖，通常指極大的連通子圖

在尋找 bridge 的過程中順便找 BCC
如果\(u\)的父邊是橋，則\(u\)往下形成一個BCC
利用 stack 紀錄

拜訪一個新的點時，將該點塞入stack
若發現 \(u\) 父邊是橋，將 stack 裡的東西取出直到 \(u\) 也被取出
這些被取出的點形成 BCC

Time Complexity

DFS: \(\mathcal{O}(V+E)\)

 const int N = 100010 ;
vector<int> g[N];
bool vis[N], bridge[N] ;
int low[N], dep[N], bcc[N], bccID ;
stack<int> stk ;
 
void dfs(int x) {
    vis[x] = true ;
    low[x] = dep[x] ;
    stk.push(x) ;
 
    for(auto i:g[x]) {
        if(vis[i]) {
            low[x] = min(low[x], dep[i]) ;
        } else {
            dep[i] = dep[x] + 1 ;
            dfs(i) ;
            low[x] = min(low[x], low[i]) ;
        }
    }
    
    if(low[x] == dep[x]) {
        bridge[x] = true ;
        ++bccID ;
        int k ;
        do {
            k = stk.top() ;
            bcc[k] = bccID ;
            stk.pop() ;
        } while(k != x) ;
    }
}

Properties

邊連通分量內：
- 任兩點至少有兩條路相通，且這兩條路沒有共用邊
- Robbin定理：存在一種將邊定向的方式，使得任兩點可以互相抵達(形成SCC)

縮點

若將每個 BCC 視為一個點，新的圖將形成一棵樹

點雙連通

沒有傳遞性：若\(x\)和\(y\)點雙連通，\(y\)和\(z\)點雙連通，無法保證\(x\)和\(z\)點雙連通
判斷一張圖是否點雙連通：移除每個點\(v\)，檢查是否整張圖還連通。

割點

cut vertex / articulation vertex(point) / AP
關節點
定義：若圖 \(G\) 在點 \(v\) 移除後會變得不連通，則稱 \(v\) 為割點

Problem

給定一張圖 \(G\)，請找出圖中所有的割點

Low Function

觀察點 \(v\) 及其小孩 \(u\)
若 \(u\) 無法不透過 \(v\) 到達祖先時，則 \(v\) 是 AP
\(\text{low}(u) \geq \text{dep}(v)\rightarrow v\) 是AP

Root

根節點是AP若且唯若他有兩條樹邊
每條樹邊下的子樹各自獨立

Time Complexity

DFS: \(\mathcal{O}(V+E)\)

點雙連通分量

stack 紀錄
若 \(v\) 是AP，則下方形成一個BCC
點雙連通分量有交集：
- AP 要放回 stack
- 改成紀錄邊 (沒有交集)

圓方樹

圓點：割點
方點：點雙連通分量

重邊

只有一條邊是父邊(樹邊)，剩下的視為回邊
額外判斷往父親走了幾次

	const int N = 100010 ;
	vector<int> g[N], rg[N], ord;
	int scc[N], sccID ;
	bool vis[N] ;

	void dfsRev(int x) {
	vis[x] = true ;
	for(auto i:rg[x])
	if(!vis[i])
	dfsRev(i) ;
	ord.push_back(x) ;
	}

	void dfs(int x) {
	vis[x] = true ;
	scc[x] = sccID ;
	for(auto i:g[x])
	if(!vis[i])
	dfs(i) ;
	}

	void kosaraju(int n) {
	for(int i=1; i<=n; ++i)
	if(!vis[i])
	dfsRev(i) ;

	reverse(ord.begin(), ord.end()) ;
	fill(vis, vis+N, 0) ;

	for(auto i:ord) if(!vis[i]) {
	++sccID ;
	dfs(i) ;
	}
	}

	const int N = 1010 ;
	vector<int> g[N];
	int py[N] ;
	bool vis[N] ;

	bool dfs(int x) {
	for(auto i:g[x]) if(!vis[i]) {
	vis[i] = true ;
	if(!py[i] \|\| dfs(py[i])) {
	py[i] = x ;
	return true ;
	}
	}
	return false ;
	}

	int APA(int n) {
	int ret = 0 ;
	for(int i=1; i<=n; ++i) {
	fill(vis, vis+N, 0) ;
	if(dfs(i)) ++ret ;
	}
	}

	struct KM {
	int n ;
	vec<vec<pii>> g ;
	vec<int> lx, ly, vx, vy, p;

	KM (int _n) {
	n = _n ;
	g.rs(n + 1) ; p.rs(n + 1) ;
	lx.rs(n + 1) ; ly.rs(n + 1) ;
	vx.rs(n + 1) ; vy.rs(n + 1) ;
	}

	void addEdge(int a, int b, int c) {
	g[a].EB(b, c);
	}

	bool dfs(int x) {
	vx[x] = true;
	for(auto [i, u]:g[x]) if(!vy[i] && lx[x] + ly[i] == u) {
	vy[i] = true;
	if(!p[i] \|\| dfs(p[i])) {
	p[i] = x ;
	return true;
	}
	}
	return false ;
	}

	int exe () {
	rep1(i, n) for(auto j:g[i])
	amax(lx[i], j.S);

	rep1(i, n) {
	while(true) {
	fill(ALL(vx), 0);
	fill(ALL(vy), 0);

	if(dfs(i)) break;

	int d = INF;
	rep1(i, n) if(vx[i])
	for(auto [j, u]:g[i]) if(!vy[j])
	amin(d, lx[i] + ly[j] - u) ;

	rep1(i, n) {
	if(vx[i]) lx[i] -= d ;
	if(vy[i]) ly[i] += d ;
	}
	}
	}

	int ret = 0;
	rep1(i, n) ret += lx[i] + ly[i] ;
	return ret ;
	}
	};

	struct KM {
	int n;
	vec<vec<int>> g;
	vec<int> lx, ly, slk, vis, pre, mat;

	KM (int _n) {
	n = _n ;
	g.assign(n+1, vec<int>(n+1, -INF));
	lx.rs(n+1); ly.rs(n+1);
	vis.rs(n+1); mat.rs(n+1);
	slk.rs(n+1); pre.rs(n+1);
	}

	void addEdge(int a, int b, int c) {
	g[a][b] = c;
	}

	void bfs(int x) {
	int px, py = 0, ny = 0, d;
	rep(i, n+1) vis[i] = pre[i] = 0, slk[i] = INF;
	mat[py] = x;

	do {
	px = mat[py], vis[py] = true, d = INF;
	rep1(i, n) if(!vis[i]) {
	if(slk[i] > lx[px] + ly[i] - g[px][i])
	slk[i] = lx[px] + ly[i] - g[px][i], pre[i] = py;
	if(d > slk[i])
	d = slk[i], ny = i;
	}
	rep(i, n+1)
	if(vis[i]) lx[mat[i]] -= d, ly[i] += d;
	else slk[i] -= d;
	py = ny;
	} while(mat[py]);
	while(py) mat[py] = mat[pre[py]], py = pre[py];
	}

	ll match() {
	rep1(i, n) bfs(i);
	ll ret = 0;
	rep1(i, n) ret += lx[i] + ly[i];
	return ret;
	}
	};

	const int N = 100010 ;
	vector<int> g[N];
	bool vis[N], bridge[N] ;
	int low[N], dep[N] ;

	void dfs(int x) {
	vis[x] = true ;
	low[x] = dep[x] ;
	for(auto i:g[x]) {
	if(vis[i]) {
	low[x] = min(low[x], dep[i]) ;
	} else {
	dep[i] = dep[x] + 1 ;
	dfs(i) ;
	low[x] = min(low[x], low[i]) ;
	}
	}
	if(low[x] == dep[x]) bridge[x] = true ;
	}

110 選手班 - 進階圖論

tags: 宜中資訊 CP

tags: `宜中資訊` `CP`