Part.2 无向图的双联通分量

点双连通图

若一张无向连通图不存在割点，则称它为“点双连通图”。

无向图的极大点双联通子图称为“点双连通分量”，简记为 “v-DCC”。

边双连通图

若一张无向连通图不存在割边，则称它为“边双联通图”。

无向图的极大边双联通子图称为“边双联通分量”，简记为 “e-DCC”。

二者统称为 “DCC”。

注：“极大”指对于一个 DCC： \(G'=(V',E') ,G' \subseteq G\)；$ \nexists G''=(V'',E'') ,G'' \subseteq G,G' \subseteq G''$ 使得 \(G''\) 也是一个 DCC。

定理

一张无向连通图是“点双连通图”，当且仅当满足下列两个条件之一：

1. 图的顶点数不超过 2

2. 图中任意两点都同时包含在至少一个简单环中，

一张无向连通图是“边双连通图”，当且仅当任意一条边都包含在至少一个简单环中。

证明

To：“点双连通图”

顶点数不超过 2，根据定义，显然成立。

充分性：若任意两点 \(x,y\) 都同时包含在至少一个简单环中，则 \(x,y\) 之间至少有两条不相交的路径，无论从图中删去哪一个节点，\(x,y\) 之间仍然可以相连（想一想前面的 BLO 那道题），所以图中没有割点。

必要性：反证法，假设一张无向连通图是“点双连通图”，并且存在两点 \(x,y\) 他们不同时处于任何一个简单环中。

如果 \(x,y\) 之间仅存在 1 条简单路径，那么肯定存在割点，与定义矛盾。

如果 \(x,y\) 之间存在 2 条及以上的简单路径，那么除了 \(x,y\) 这两个交点，任意两条路径都必须至少有一个交点，进而得知他们肯定至少都交于一点，那该交点根据定义就是一个割点，与定义矛盾；如果不相交，就会出现简单环，就与假设矛盾了。

To：“边双连通图”

充分性：如果所有边都包含在至少一个简单环中，那么无论切去哪条边，剩下的所有节点仍然可以连通，故不存在割边。

必要性：反证法，假设一张无向连通图是“边双连通图”，并且存在一条不包含在任意一个简单环中的边。

那么它的端点 \(x,y\) 也不包含在任意一个简单环中，所以这条边是 \(x,y\) 之间的唯一通路，切去这条边以后，\(x,y\) 就不连通了，那么这条边就是割边，与定义矛盾。

e-DCC 的求法

对无向图进行判桥，然后把桥挖掉，剩下的就是无向图中全部的 e-DCC。

e-DCC 的缩点

先说一句，挖一个坑，听说 LCT 可以动态地在只加边的情况下完成这个过程，以后做 LCT 的时候再填坑。

很简单，把每个 e-DCC 看成一个大点，内部的边不要，只留下链接两个不同 e-DCC 之间的边，建一个新图，新图的形态是一棵树或森林。

v-DCC 的求法

维护一个栈，用以下方法维护栈中的元素：

1. 当一个节点首次被访问时，把该节点入栈。

2. 当割点判定法则中的条件 \(dfn[x] \leq low[y]\) 成立时，无论 \(x\) 是否为根，都要从栈中不断弹出节点直到节点 \(y\) 被弹出；且刚才弹出的所有节点和节点 \(x\) 一起构成一个 v-DCC 。

v-DCC 的缩点

因为一个节点可能属于多个 v-DCC，设图中有 \(p\) 个割点和 \(t\) 个 v-DCC。然后建立一张包含 \(p+t\) 个节点的新图，把每个 \(v-DCC\) 和每个割点都作为新图中的节点，并且在每个割点和包含它的所有 v-DCC 之间连边。

建成的新图也是一棵树或森林。

参考题目： POJ3694 Network / AcWing364 网络

第一眼看到这狗东西，这不是我以前看见过的一个 LCT 在只加边的情况下动态维护无向图桥数量的题目吗？

然后一看数据范围，缩点，纯暴力标记法，可以过。

但我们不能局限于暴力，我们要优化。

先缩一个点，然后建一棵树，拎起来，预处理好树的父子结构和深度。

对于每个节点，开一个并查集（带路径压缩），初始 \(fa[x]\) 就是自己，表示所属的 e-DCC 集合。

每次来一个询问，若当前两个节点属于同一个 e-DCC （用 \(find(x)\) 找），那就忽略。

如果不属于同一个 e-DCC ，那么像 LCA 暴力上跳法一样，对于两个节点所属的 e-DCC ，在树上跳到父亲，且每次把当前节点的 \(fa[x]\) 指向自己在原树上的父亲，之后就可以愉快的路径压缩了。此过程中，统计跳过的边数，这些边就不再是桥了。

参考代码：

#include
#define pb push_back
using namespace std;

const int maxn=100010,maxm=200010;

int n,m;

struct edge{
	int to,ch;
};
int vis[maxm];

vectorgo[maxn];

int dfn[maxn],low[maxn],isb[maxm],tim=0,cnt=0;
int stk[maxn],top=0;

vectorng[maxn];

int fa[maxn],f[maxn],dep[maxn];
int from[maxn];

int getfa(int x){
	return (fa[x]==x)?(x):( fa[x]=getfa(fa[x]) );
}

int jump(int x,int y){
	int res=0;
	while(getfa(x)!=getfa(y)){
		if(dep[getfa(x)]dfn[x]){
				isb[tmp.ch]=1;
			}
		}
		else{
			low[x]=min(low[x],dfn[tmp.to]);
		}
	}
	if(dfn[x]==low[x]){
		int tmp;
		cnt++;
		do{
			tmp=stk[top--];
			from[tmp]=cnt;
		}while(tmp!=x);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	
	int cas=0;
	
	while(cin>>n>>m){
		if(n==0&&m==0)break;
		
		for(int i=1;i>u>>v;
			go[u].pb(edge{v,i});
			go[v].pb(edge{u,i});
		}
		
		tarjan(1,0);
		
		int ans=0;
		
		for(int i=1;i<=n;i++){
			for(edge tmp:go[i]){
				if(vis[tmp.ch]||isb[tmp.ch]==0)continue;
				vis[tmp.ch]=1;
				ans++;
				ng[from[i]].pb(from[tmp.to]);
				ng[from[tmp.to]].pb(from[i]);
			}
		}
		
		dfs(1,0);
		
		int q;
		
		cin>>q;
		
		cout<<"Case "<<++cas<<":"<>u>>v;
			if(getfa(from[u])!=getfa(from[v]))
			ans-=jump(getfa(from[u]),getfa(from[v]));
			cout<

#include
#include
#define si short int
#define re register

const si maxn=1010;
const int maxm=1000010;
const char z='0';

si inr[maxn];

si n;int m;

struct edg{
	si u,v;
}e[maxm];

bool g[maxn][maxn];

si stk[maxn],top;
si dfn[maxn],low[maxn],tim;
bool dcc[maxn];
si ind[maxn],hed;

inline void init(){
	re si u,v;
	for(re int i=1;i<=m;++i){
		 u=e[i].u,v=e[i].v;
		g[v][u]=g[u][v]=true;
	}
	tim=0;
	for(re si i=1;i<=n;++i){
		dfn[i]=low[i]=inr[i]=0;
	}
}

inline si in(){
	re si res=0;
	re char tp=getchar();
	while(!isdigit(tp))tp=getchar();
	while(isdigit(tp))res=res*10+tp-z,tp=getchar();
	return res;
}

inline int inm(){
	re int res=0;
	re char tp=getchar();
	while(!isdigit(tp))tp=getchar();
	while(isdigit(tp))res=res*10+tp-z,tp=getchar();
	return res;
}

inline si minn(const si &x,const si &y){
	return (x=dfn[x]){
				re si tmp;
				hed=0;
				do{
					tmp=stk[top--];
					dcc[tmp]=true;
					ind[++hed]=tmp;
				}while(tmp!=y);
				dcc[x]=true;
				ind[++hed]=x;
				re si p;
				re bool res=!judge(x,0);
				while(hed){
					p=ind[hed];
					dcc[p]=false;
					inr[p]|=res;
					col[p]=-1;
					--hed;
				}
			}
		}
		else low[x]=minn(low[x],dfn[y]);
	}
}

int main(){
	//memset(col,0xcf,sizeof(col));
	for(re si i=1;i

#include
#define pb push_back
#define ull unsigned long long
using namespace std;

int n;

int maxx;

vectorgo[1010];
vectorvdcc[1010];int tot;
int gd[1010];


int dfn[1010],low[1010],rt,ord;
int sta[1010],top=0;
void tarjan(int x){
	low[x]=dfn[x]=++ord;
	sta[++top]=x;
	int is=0;
	for(int to:go[x]){
		
		
		if(!dfn[to]){
			tarjan(to);
			low[x]=min(low[x],low[to]);
			if(dfn[x]<=low[to]){
				is++;tot++;
				if(x!=rt||is>1)gd[x]=1;
				int tmp=0;
				do{
					tmp=sta[top--];
					vdcc[tot].pb(tmp);
				}while(tmp!=to);
				vdcc[tot].pb(x);
			}
		}
		else{
			low[x]=min(low[x],dfn[to]);
		}
		
	}
	//if(x==rt&&is>=2)gd[x]=1;
	//else if(is>=1)gd[x]=1;
}

void initialize(){
	maxx=0;
	tot=0;
	ord=0;
	top=0;
	for(int i=1;i<=1000;i++){
		go[i].clear();
		vdcc[i].clear();
	}
	memset(gd,0,sizeof(gd));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	
	int cas=0;
	while(cin>>n&&n){
		cas++;
		initialize();
		
		ull ans1=0,ans2=1;
		
		int u,v;
		for(int i=1;i<=n;i++){
			cin>>u>>v;
			maxx=max(u,maxx);
			maxx=max(v,maxx);
			go[u].pb(v);
			go[v].pb(u);
		}
		
//		for(int i=1;i<=maxx;i++){
//			
//			if(!dfn[i]){
//				rt=i;
//				tarjan(i);	
//			}
//			
//		}
		rt=1;
		tarjan(1);
		
		for(int i=1;i<=tot;i++){
			int gdt=0;
			ull siz=vdcc[i].size();
			for(int tmp:vdcc[i]){
				if(gd[tmp])gdt++;
			}
			if(gdt==0){
				ans1+=2;
				ans2*=(siz*(siz-1ull)/2ull);
			}
			else if(gdt==1){
				ans1++;
				ans2*=(siz-1ull);
			}
		}
		
		cout<<"Case "<

#include
#define pb push_back
using namespace std;

const int maxn=1010,maxm=30010;

int n,m,s,t;

int ans=0x7fffffff;
int c;
int s1,s2;

struct edge{
	int to,len,ord;
};

int u[maxm],v[maxm],w[maxm];

vectorgo[maxn];

int vis[maxn];
bool dfs(int x,int fa,int del,vector&path){
	vis[x]=1;
	if(x==t)return true;
	for(edge tmp:go[x]){
		if(tmp.to==fa||vis[tmp.to]||tmp.ord==del)continue;
		if(dfs(tmp.to,x,del,path)){
			path.pb(tmp.ord);
			return true;
		}
	}
	return false;
}

int dfn[maxn],low[maxn],gb[maxm],seq=0;
//int stk[maxn],top=0;

void tarjan(int x,int come,int del){
	//stk[++top]=x;
	low[x]=dfn[x]=++seq;
	
	for(edge tmp:go[x]){
		if(tmp.ord==del||tmp.ord==come)continue;
		if(!dfn[tmp.to]){
			tarjan(tmp.to,tmp.ord,del);
			low[x]=min(low[x],low[tmp.to]);
			if(low[tmp.to]>dfn[x]){
				gb[tmp.ord]=1;
			}
		}
		else{
			low[x]=min(low[x],dfn[tmp.to]);
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	
	cin>>n>>m;
	
	cin>>s>>t;
	
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		go[u[i]].pb((edge){v[i],w[i],i});
		go[v[i]].pb((edge){u[i],w[i],i});
	}
	
	vectorpath;
	path.clear();
	
	if(!dfs(s,0,0,path)){
		cout<<"0"<np;
		np.clear();
		
		memset(vis,0,sizeof(vis));
		if(!dfs(s,0,now,np)){
			if(w[now]<=ans){
				ans=w[now];
				c=1;
				s1=now;
			}
			continue;
		}
		
		seq=0;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(gb,0,sizeof(gb));
		tarjan(s,0,now);
		
		for(int tmp:np){
			if(!gb[tmp])continue;
			if(w[now]+w[tmp]=0x7fffffff)cout<<"-1"<