自动搬运

查看原文

来自洛谷，原作者为

	Larryyu Euphoric NocturNe |AS| ALTERing EGO

搬运于2025-08-24 23:12:36，当前版本为作者最后更新于2025-08-03 22:47:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

有一张 $n$ 个点，$m$ 条边的有向图。

Bob 不知道原图具体形态，但知道哪些点在同一强连通分量中。

Alice 要将一些边改为无向边，使得 Bob 可以确定每条无向边在原图中的方向。

求最多能改多少条边，以及方案数对 $10^9+7$ 取模的结果。

保证任意两点之间最多只有一条边，无论方向如何。

$2\le n\le2000,1\le m\le2000$。

Solution

下文中，$u\rightsquigarrow v$ 表示 $u$ 到 $v$ 的一条路径。

先考虑缩完点后在DAG上的边。

对于边 $u\to v$，如果删去该边后依然存在 $u\rightsquigarrow v$，那么可以改为无向边，因为反向后会有新的SCC生成。

注意缩点后的图可能有重边，如果不满足上面的条件，则重边中要保留一条。

此部分可以 $O(n+m)$，本文代码为 $O(nm)$。

再考虑SCC内部的边，接下来的原图为单个SCC。

如果删去 $u\to v$ 后不改变原图连通性，则不能变无向边，因为无法确定方向。

否则 $u\to v$ 反向后一定改变原图连通性。

因为 $u\to v$ 属于一个SCC，所以一定有 $v\rightsquigarrow u$，只有这上面的边影响 $u\to v$ 能否变无向边。

于是考虑删掉 $u\to v$ 后所点形成的DAG，其中 $u$ 的出度和 $v$ 的入度一定为 $0$，再将 $u\to v$ 放回去，设这张图为 $G_{u,v}$。

每条边都对应一张这样的图，而每张这样的图都与其中SCC集合形成双射，所以一条边可以用一个SCC集合表示。

引理：

若两条边的SCC集合不同，那两条边之间是否删除方向互不影响。

证明：

设两条边分别为 $u\to v$ 和 $x\to y$。

因为其SCC集合不同，所以两条边不可能同时在对方缩完点后的DAG上。

若两条边都不在对方DAG上则显然互不影响。

否则设 $x\to y$ 在 $u\to v$ 的DAG上，也就是 $u\to v$ 在 $x\to y$ 的DAG上被缩在了一个SCC里面，设其为 $A$，如果 $u\to v$ 最后删向也要先保证 $A$ 的连通性，只要 $A$ 连通，内部边是否删向对 $x\to y$ 能否删向没有影响。

同理，在 $x\to y$ 的DAG上，$x\to y$ 是否删向都要先保证 $A \rightsquigarrow x\to y \rightsquigarrow A$ 这条路径只能唯一定向，而 $u\to v$ 在 $A$ 中不影响这条路径，所以这条路径在 $u\to v$ 的DAG上是固定方向的，与 $x\to y$ 是否删向无关。

于是我们可以将SCC集合相同的边分到一组一起考虑，不同组之间互不影响。

对于一组边 $E$，设这种边的数量为 $c1$，对应的SCC集合中SCC的数量为 $c2$，有 $c2\ge c1$。

因为这组边对应的 $G$ 上，存在一个环使得 $E$ 是其边集的子集，且对于非环边 $u\to v$，环上路径 $u\rightsquigarrow v$ 的边集与 $E$ 无交。

若 $c2=c1$ 即环的边集就是 $E$，那至少要保留一条边有方向，方案数为 $|E|-1$。

否则 $c2>c1$ 则 $E$ 全都可以删向，方案数为 $|E|$。

对于不同组的边，由于互不影响，方案数由乘法原理可知相乘即可。

时间复杂度 $O(nm)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
mt19937 rnd(time(0));
const int N=2020,M=2020,mo=1e9+7;
int n,m,g,cnt,tot;
ll ans1,ans2=1;
ull hsh;
int u[N],v[N],col[N],dfn[N],low[N];
int fl[N][N],hs1[N],hs2[N];
bool vis[N],ext[N][N];
stack<int> s;
vector<int> e[N];
map<pair<int,ull>,int> mp;
void dfs(int x,int &t,int op){
	dfn[x]=low[x]=++cnt;
	vis[x]=1,s.push(x);
	for(int y:e[x]){
		if(ext[x][y]) continue;
		if(!dfn[y]){
			dfs(y,t,op);
			low[x]=min(low[x],low[y]);
		}else if(vis[y])
			low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		t++;
		ull tmp=0;
		int num=1;
		while(s.top()!=x){
			if(op) col[s.top()]=t;
			vis[s.top()]=0;
			tmp^=hs1[s.top()],num++;
			s.pop();
		}
		if(op) col[x]=t;
		vis[x]=0;
		hsh+=(tmp^hs1[x])*hs2[num];
		s.pop();
	}
}
void alter(int x){
	vis[x]=1;
	for(int y:e[x])
		if(!vis[y]) alter(y);
}
bool check(int x,int y){
	for(int i=1;i<=tot;i++) vis[i]=0;
	for(int z:e[x]){
		if(y==z||vis[z]) continue;
		alter(z);
	}
	return vis[y];
}
void solve(int x){
	hsh=0;
	mp.clear();
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1;i<=m;i++)
		if(col[u[i]]==col[v[i]]&&col[u[i]]==x) e[u[i]].push_back(v[i]);
	for(int i=1;i<=m;i++){
		if(col[u[i]]!=col[v[i]]||col[u[i]]!=x) continue;
		int tmp=0;
		ext[u[i]][v[i]]=1,hsh=0;
		e[v[i]].push_back(u[i]);
		cnt=hsh=0;
		for(int i=1;i<=n;i++) dfn[i]=low[i]=0;
		for(int i=1;i<=n;i++)
			if(col[i]==x&&!dfn[i]) dfs(i,tmp,0);
		mp[{tmp,hsh}]++;  //求出这条边对应的SCC集合
		e[v[i]].pop_back();
		ext[u[i]][v[i]]=0;
	}
	for(auto [h,b]:mp){
		int a=h.first;
		if(a==1) continue;  //SCC集合大小为1说明这条边是否存在不影响连通性
		if(b==a) ans1+=b-1,ans2=ans2*b%mo;
		else ans1+=b;  //对于每一组边分开算贡献
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>n>>m>>g;
	for(int i=1;i<=n;i++) hs1[i]=rnd(),hs2[i]=rnd();
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i];
		e[u[i]].push_back(v[i]);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) dfs(i,tot,1);
	}
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1;i<=m;i++){
		int x=col[u[i]],y=col[v[i]];
		if(x==y) continue;
		if(!fl[x][y]) e[x].push_back(y);
		fl[x][y]++;
	}
	for(int i=1;i<=tot;i++){
		for(int j=1;j<=tot;j++){
			if(!fl[i][j]) continue;
			if(check(i,j)) ans1+=fl[i][j];
			else ans1+=fl[i][j]-1,ans2=ans2*fl[i][j]%mo;
		}  //计算原图缩点后DAG上的边产生的贡献
	}
	for(int i=1;i<=tot;i++) solve(i);  //单个SCC考虑
	cout<<ans1<<'\n'<<ans2<<'\n';
	return 0;
}