前言

連通性問題確實時一大比較難啃得蛋糕，每次都要先學習一遍，還不如一次學到通

無向圖的連通性問題

求割點

連通圖：連通圖內的所有點都可以互相到達
割點：將割點刪掉后整張圖不連通

定理1：

一個點s是割點，當且僅當s作為該連通圖的根時，會把連通圖分為不相連的幾部分

定理2：

一個非根節點u是割點，當且僅當u存在一個子節點v不存在一條邊連向u的祖先

一開始我認為只要存在一條邊連向祖先就不算割點，但這里舉出反例：

實現

考慮dfs序，就是將節點編號為dfs遍歷到的順序
我們設一個dfn表示dfs序，設low表示當前節點能回到的最大祖先的編號，只要存在子節點v的\(low[v]>=dfn[u]\) 就可以了

代碼

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
int n,m,u,v,tot,ans;
int dfn[N],low[N],vis[N],dot[N];
vector<pii>b[N];
void dfs(int x,int nxt){
	dfn[x]=low[x]=++tot;
	vis[x]=1;
	bool cnt=0;
	int num=0;
	for(auto i:b[x]){
		if(nxt==i.second)  continue;//這里大抵是沒有用的
		int k=i.first;//要開局部變量，不要像我一樣手懶開全局變量寄掉
		if(!vis[k]){
			num++;
			dfs(k,i.second);
			low[x]=min(low[x],low[k]);
			if(low[k]>=dfn[x])  cnt=1;
		}
		else{
			low[x]=min(low[x],dfn[k]);//無向圖中也可以寫low
		}
	}
	if(!nxt){
		if(num>1)  dot[++ans]=x;//注意特判根節點的情況
	}
	else if(cnt){
		dot[++ans]=x;
	}  
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back({v,i});
		b[v].push_back({u,i});
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i,0);
		}
	}
	sort(dot+1,dot+ans+1);
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++){
		printf("%d ",dot[i]);
	}
}

割邊

只需要把 \(low[v]>=dfn[u]\) 改成 \(low[v]>dfn[u]\) 就行了，因為u的所有后代都到達不了v，從u->v的邊一定是割邊

邊雙連通分量

在邊雙連通分量中，兩點間存在至少兩條邊不重復的路徑
類似于割點的辦法，但有所不同
將遍歷到的點放入棧，若一個點滿足 \(low[v]>=num[u]\)，則將這個點作為這個邊雙連通分量中的頭，將棧中在它上面的點依次彈出，這之中的點就構成了點雙連通分量

點雙連通分量

同理兩點間存在至少兩條點不重復的路徑
把邊雙改一下棧中存的是邊就可以了
因為點雙中一個點可能在多個點雙之中
不信，你畫個8試試

有向圖的連通性問題

tajan

其實和邊雙寫法一樣，我記得以前有人說回溯邊只能用dfn不能用low，但是我證實了是可以的！不過也不保準
為什么要用vis數組記錄是否在棧中呢？
因為不在棧中的點代表已經單獨構成強連通分量了，不可能再與這個點構成強連通分量了，若有橫叉邊，就是從這個強連通分量到另一個強連通分量，但是這條邊并不會到達它的祖先不符合low的定義，反而一定會影響其的low值，所以只能用棧中的點更新
可以用此圖直觀表示一下：

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int dfn[N],low[N],vis[N],s[N],col[N],en[N],a[N],num[N],vi[N],dp[N];
int cnt,colnum,n,m,u,v,top,ans;
vector<int>b[N];
vector<int>newb[N];
void dfs1(int x){
	dfn[x]=low[x]=++cnt;
	s[++top]=x;
	vis[x]=1;
	for(auto i:b[x]){
		if(!dfn[i])  dfs1(i);
		if(vis[i])  low[x]=min(low[x],low[i]);
	}
	if(low[x]==dfn[x]){
		colnum++;
		while(s[top]!=x){
			col[s[top]]=colnum;
			num[colnum]+=a[s[top]];
			vis[s[top]]=0;
			top--;
		}
		col[x]=colnum;
		num[colnum]+=a[x];
		vis[x]=0;
		top--;
	}
}
void dfs2(int x){
	vi[x]=1;
	for(auto i:newb[x]){
//		printf("神金%d %d\n",x,i);
		if(!vi[i])  dfs2(i);
//		printf("他媽%d %d\n",x,i);
		dp[x]=max(dp[x],dp[i]+num[x]);
		ans=max(dp[x],ans);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])  dfs1(i);
	}
	for(int i=1;i<=colnum;i++){
		dp[i]=num[i];
		ans=max(dp[i],ans);
	}
	for(int i=1;i<=n;i++){
		for(auto j:b[i]){
			if(col[i]!=col[j]){
				newb[col[i]].push_back(col[j]);
//				printf("草%d %d\n",col[i],col[j]); 
				en[col[j]]++;
			}  
		}
//		printf("傻逼%d %d\n",i,col[i]);
	}
	for(int i=1;i<=colnum;i++){
		if(!en[i]){
//			printf("dfs=%d\n",i);
			dfs2(i);
		}
	}
	printf("%d",ans);
}

ybtoj練習題

3.4.2

一個強連通分量里的牛都是互相喜歡的，所以我們先縮點，然后判斷那個點出度為0，因為他不喜歡任何的牛，說明他被所有奶牛喜歡，但如果有兩個出度為0的點，就說明這兩頭牛都不互相喜歡，就沒有解

3.4.3

口胡了
縮完點后，跑一遍拓撲排序，然后考慮dp轉移，若u的答案可以更新v，則可以將v的答案更新為 \(dp[u]+num[v]\)，然后v的答案個數為 $ans[u]
若u的答案等于v，則可以將v答案的個數加上u答案個數，就做完了

3.4.4

首先考慮將所有限制轉為同一限制，發現所有限制都可以表示成 \(a+k\leq b\)，因為 \(a<b => a+1\leq b\)，然后所以就將每一條限制轉化為a向b連上一條邊權為k的邊，然后縮點，若一個強連通分量中有邊權為1的邊則一定不合法，否則從入度為0的點值為1開始遞推即可

3.4.5

縮點后跑最短路即可，注意不用判重邊

3.4.6

某個傻逼縮完點后跑了一遍最小生成樹，然后發現樣例過不了，手模了一下，開始懷疑最小生成樹的正確性，忽然想到它是有向圖。。。。。。

縮完點后，它是一張0號點可以到達任意點的圖，因為它本身就滿足1號點可以到任意點，考慮刪去不優的邊，最終成一個類似于樹的圖，且要求邊權相加最短

考慮樹（和樹不同，是一張由父節點指向子節點的圖）的性質，就是每個節點除了根節點，入度都為1，所以每個節點貪心的保留入度的邊邊權最小的就行

3.4.7

考慮縮點，然后找到一條最長鏈即可

3.4.8

我們把有約束關系的連一條有向邊，如果出現環，就說明這環內的所有點必須選或不選，然后樹上背包即可

這里留一個問題：為什么不能在縮點之前建虛擬根呢？

3.4.9

口胡了一半，但是沒有發現只有n個點有寶藏這個題目的要求

首先我們只需要對有寶藏的點互相連邊即可

其次我口胡了出來，對于橫豎連邊的點，我們只需要針對一行或一列建一個虛擬點，這個點和這一行/列所有有寶藏的點連邊即可

然后因為我們只針對有寶藏的點連邊，所以我們按一下方式重新建圖，map存一下宮室位置即可