P11508 题解

tarjan 算法中 edcc 缩点。

题目传送门。

题目描述

在一个无向简单连通图 $G$ 中求出一个最小的非空子集 $S$，满足对于 $\forall x\in \complement_S G$，在删去任意一条边时，都 $\exists y \in S$，使 $x$ 和 $y$ 之间存在路径。

输出 $S$ 的最小大小，以及有多少这样的集合 $S$ 满足。

题目思路

可以先从特殊性质入手，手模发现对于任意一棵树，只须将其叶结点加入集合 $S$ 即可满足题意。

那么扩展一下，对于任意一个边双连通分量中，只需要选一个节点即可，那么考虑将原图 $G$ 进行 edcc 缩点，统计度为 $1$ 的 edcc 数量即可。

那么个数就是 $\prod_{i=1}^{k} siz_i$，其中 $siz_i$（$1\le i\le k$）就是对应度边双连通分量有多少个节点（考虑到任意点只会出现在有且仅有 1 个边双连通分量中）。

注意如果只有一个边双连通分量，则需要输出 1 和 节点个数。

求边双连通分量用 tarjan，模板题在此。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll mod=1e9+7;
int n,m;
vector<pair<int,int> > g[N];
vector<int> edcc[N];
stack<int> st;
int tot=0,cnt=2,low[N],dfn[N];
int num,edccno[N];
int d[N];
void tarjan(int u,int in_edge){
	low[u]=dfn[u]=++tot;
	st.push(u);
	for(auto d:g[u]){
		int v=d.first,idx=d.second;
		if(!dfn[v]){
			tarjan(v,idx);
			low[u]=min(low[u],low[v]);
		}
		else if(dfn[v]<dfn[u]&&idx!=(in_edge^1)){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++num;
		while(1){
			int v=st.top();st.pop();
			edccno[v]=num;
			edcc[num].push_back(v);
			if(v==u) break;
		}
	}
}    //tarjan edcc
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		g[u].push_back({v,cnt++});
		g[v].push_back({u,cnt++});
	}
	tarjan(1,0);
	for(int i=1;i<=n;i++){
		for(auto x:g[i]){
			int v=x.first;
			if(edccno[i]!=edccno[v]){
				d[edccno[i]]++;
				d[edccno[v]]++;
			}
		}
	}
	if(num==1){
		cout<<"1 "<<n;    //注意特判
		return 0;
	}
	for(int i=1;i<=num;i++) d[i]/=2;    //度会被统计2次
	vector<int> arr;
	for(int i=1;i<=num;i++){
		if(d[i]==1) arr.push_back(i);
	}
	cout<<arr.size()<<" ";
	ll ans=1;
	for(auto i:arr){
		ans=ans*(1ll*edcc[i].size())%mod;    //求出答案
	}
	cout<<ans;
	return 0;
}

谢谢阅读。