You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

题解 P2661 【信息传递】

. 1 min read

十分奇特的递归做法

考虑边数为n,点数为n.所以我们可以得到若一点入度为0,则删去该点以及它的出边对图上的环都没有影响.

在对全图进行一次删点删边之后就可以得到新图,其中可能含有新的入度为0的点.

所以同样继续处理,直到图中不存在入度为0的点.

如下图操作

所以递归处理如图

此时我们可以得到一个图,其出度入度全为1

之后再次简单遍历一遍环就可以求出答案

下面是渣渣代码
没写快读,可能有点慢

用时: 119ms / 内存: 2320KB

#include <iostream>
#define N 200005
#define INF 200005
using namespace std;
int to[N],indgree[N];
bool visit[N];
int n;
void delzero(){//删点操作
	bool flag=1;
	for (int i=1;i<=n;i++){
		if (indgree[i]==0&&!visit[i]){
			flag=0;
			visit[i]=1;
			indgree[to[i]]--;
		}
	}
	if (flag) return;
	else delzero();
	return;
}
int ans=INF;
void search(int start,int now,int step){//遍历环操作
	if (start==now) {ans=min(ans,step);return;}
	visit[now]=1;
	search(start,to[now],step+1);
	return;
}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>to[i];//渣渣输入
		indgree[to[i]]++;//计算入度
	}
	delzero();//删点
	for (int i=1;i<=n;i++){
		if(!visit[i]){
			visit[i]=1;
			search(i,to[i],1);//遍历环
            //是(i,to[i],1)而不是(i,i,0)被坑了
		}
	}
	cout<<ans<<endl;
	return 0;
}


本站总访问量