「CEOI2012」 Network 题解

题意

(~~~~) 给出一幅 (n) 个点，(m) 条边的有向图。定义从 (p) 可以到达 (q)，当且仅当不存在两条从 (p) 到 (q) 的路径其边集交集为空。同时保证图中有一个节点 (r) ，它可以到达所有点。求出每个顶点可以到达多少个顶点（A）以及最少的加边方案使得任意两个顶点互相可达（B）。同时保证B问题有解。

(~~~~) (1leq nleq 10^5,1leq mleq 5 imes 10^5)。

本文版权归 Azazel 与博客园共有，欢迎转载，但需保留此声明，并给出原文地址，谢谢合作。

原文地址：https://www.cnblogs.com/Azazel/p/15240429.html

题解

(~~~~) ~~根据题解反推题意太草了。~~

(~~~~) 本题重点在于找出原始图的形态特点并考虑缩点后及求解过程中将会保持的形态特点，之后的问题将迎刃而解。

(~~~~) 由于保证B问题有解，即初始给出的图不会使得某个两个点之间有两条不相交的路径，因此我们可以推出原图的形态为一棵树加上若干条返祖边。考虑若某条非树边 (u ightarrow v) 不是返祖边，则这两个点的 LCA 到 (v) 的路径会不唯一，故证得所有非树边必定为返祖边。

(~~~~) 先来思考怎么做问题A，由于一个环内的点的答案都是一样的，所以我们可以缩点来统计答案。由于有上面关于图的形态的保证，缩点后得到的图一定是一棵以 (r) 为根的有根外向树。因此每一个缩点后的强连通分量的答案即为其子树内原节点的个数和。

(~~~~) 再来考虑问题B，问题B即让我们把所有点串成一个强连通分量。由于有上面的分析，我们加入的边也一定都是返祖边。因此我们需要做的是加入最少的返祖边使得每条边仅刚好属于一个简单环。（若属于多个环则必定会出现一对点之间的路径不唯一）考虑贪心覆盖，则每个点只需要暴力往上跳所有未被简单环包含的边并向最后跳到的点连边即可。为了同时保证选择的初始点最优，我们每次选择非环边出度最小的点，进行类似拓扑排序的连边即可。

(~~~~) 时间复杂度：(mathcal{O(n+m)})。

代码

(~~~~) 本题应该也不会有人拿别人代码去对拍，所以这里放出的代码略去了部分无关紧要的地方。

查看（屎山）代码

#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
int n,m,r;
stack<int>S;
bool InStack[100005];
int dfn[100005],low[100005],Times,tot,Out[100005];
int dep[100005],Ans1[100005],belong[100005],siz[100005],Fa[100005];
vector < PII > G[100005],G_[100005];
void Tarjan(int u){··· ···}
void dfs(int u,int fa){··· ···}//求解问题1的dfs
struct Edge{
	int u,v;
	Edge(){}
	Edge(int U,int V){u=U,v=V;}
}E[500005];
queue<int>q;
map<int,bool>vis[100005];
void Tag(int u,int fa)
{
	Fa[u]=fa;
	dep[u]=dep[fa]+1;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i].first;
		if(dep[v]<dep[u]&&dep[v]) continue;//注意不能走返祖边，因为此处为找父节点，且返祖边必定包含在环内，不需考虑
		Tag(v,u);
	}
}
vector < PII > Ans2;
void TopSort()
{
	for(int i=1;i<=n;i++) if(!Out[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		int x=u;
		while(x!=r)
		{
			if(vis[x][Fa[x]]) break;
			vis[x][Fa[x]]=true;x=Fa[x];
		}
		if(x&&x!=u) Ans2.push_back(mp(u,x));//注意没有跳时不需要连边
		if((--Out[x])==0) q.push(x);
	}
}
template<typename T>void read(T &x){··· ···}//快读
template<typename T>void print(T x){··· ···}//快输
int main() {
	read(n);read(m);read(r);
	for(int i=1,u,v;i<=m;i++)
	{
		read(u);read(v);
		E[i]=Edge(u,v);G[u].push_back(mp(v,i));
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=n;i++) G[i].clear();
	for(int i=1;i<=m;i++)
	{
		int x=belong[E[i].u],y=belong[E[i].v];
		if(x!=y) G[x].push_back(mp(y,i)); 
	}
	dfs(belong[r],0);
	for(int i=1;i<=n;i++) print(Ans1[belong[i]]),putchar(' ');
	puts("");
	for(int i=1;i<=tot;i++) G[i].clear();
	for(int i=1;i<=m;i++)
	{
		G[E[i].u].push_back(mp(E[i].v,i));
		G_[E[i].v].push_back(mp(E[i].u,i));
		if(belong[E[i].u]==belong[E[i].v]) {vis[E[i].u][E[i].v]=vis[E[i].v][E[i].u]=true;continue;}
		Out[E[i].u]++;
	}
	Tag(r,0);TopSort();
	print(Ans2.size());puts("");
	for(int i=0;i<Ans2.size();i++) print(Ans2[i].first),putchar(' '),print(Ans2[i].second),puts("");
	return 0;
}