题解 P2661 【信息传递】

首先介绍个概念：基环外向树，也叫环加外向树，环基树，章鱼图。

这就是一颗基环外向树。

不难发现，若基环外向树有n个结点就有n条边，这也意味

着它不是颗普通的树，而是必定有一个自环。

再看看题目中的介绍：

通过注意里这句话可以知道每个点只有一个出度却可能有

多个入度。所以呢，它一定存在一个或多个自环（不然这

游戏永远无法结束）但也可能有普通的树（见图1的蓝点）

于是我们只需建图，这个图就是基环外向树，找出图中的

所有自环，或称之为环基树，然后算出所有

环基数中最小环的长度就是我们的答案。

具体怎么建图找环呢？请看代码。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int maxn=200000;

struct Edge

{

	int to,ne;

} edge[maxn];

int num_edge=0,h[maxn];

int n;

int vis[maxn];

int ans=9999999;

int s;

bool flag=0;

int time=0;

template<class T>void read(T &x)

{

     x=0;int f=0;char ch=getchar();

     while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}

     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

     x=f?-x:x;

     return;

}

void add_edge(int f,int t)

{

	edge[++num_edge].ne=h[f];

	edge[num_edge].to=t;

	h[f]=num_edge;

}

void loop(int x)

{

    if(vis[x]==1)//找到环

	{

	 vis[x]=3;

	 time=0;

	 s=x;

	 return;}

    vis[x]=1; //标记为已走过但不是已知环上的一点

	for(int i=h[x];i;i=edge[i].ne)

    {

    	int son=edge[i].to;

    	if(vis[son]!=3)//儿子不在环上

    	{

    	loop(son);

    	if(son==s&&time!=0)flag=1;

		//如果环已经回溯完，这个time记录了环的长度

		//即从一个相同的点绕一圈走到相同的点

    	if(!flag)time++,vis[x]=3;

        //如果是在环上的点

    	if(flag)vis[x]=0;

        //如果不在环上标记清零

		return ;

        }

        vis[x]=0;//注意写这一步

    	return ;

    }

}

int main()

{

	int anss=999999999;

	cin>>n;

	for(int i=1;i<=n;i++)

	{

		int x;

	    read(x);

		add_edge(i,x);

	}

	for(int i=1;i<=n;i++)

	{

    //任取一点，沿着出边一直走，

    //走到已经经过过了的点就找到了环

    //time类似于时间戳，

    //记录开始dfs的点绕一圈回溯走的步数即环长

		if(vis[i]!=3)

		{

		s=0;

		flag=0;

		loop(i);

		anss=min(anss,time);

	    }

    }

	cout<<anss<<endl;

	return 0;

}

只跑了40ms，对比了一下其他人的应该是比较快的（无O2）

但是这道题一开始用了两遍dfs做，结果T了。

后面优化后又忘记加上注意的那一步只过了三个点，后面静态查错才找出来，以后做题一定要三思而后行啊

话说我这个提高组的在道普及-的题目上花了这么久（逃）

巴特西

题解 P2661 【信息传递】

最新文章

热门文章