题目链接

题意分析

对于每一个点i 都指向一个点fi 从而形成一个有向图

请问至少添加多少条边 可以将原图变成一个强连通图 并输出任一方案

啥是强连通图

对于一个有向图D 如果任意点vi,vj且vi≠vj

满足从vi到vj 从vj到vi 都存在一条路径使得其连通 那么有向图D就是强连通图

首先 我们可以明白的 这个有向图中的强连通分量中的点之间肯定是不用再连边了

所以我们使用Tarjan缩点 这样就得到了若干个DAG

同时 由于这道题中的一个点只存在一个出度 所以一个DAG中的有向边替换成无向边之后就是成为了一棵树

所以 从某种意义上 我们得到了一片森林

接下来就是怎么连边了

首先 树和树之间肯定是要连接的 我们将一棵树看成一个点 也就是将其连成一个环

具体到一棵树上的话 我们让叶子节点 也就是入度为零的点 顺次相连

这样连接的话 我们发现仍然存在一个入读为零的点

如果森林中只用一棵树的话 我们让这棵树的根节点与那个入度为零的叶子节点相连

如果森林中存在多棵树的话 我们让这棵树的根节点与下一棵树的入度为零的叶子节点相连

至于统计数量的话 就是树的数量+Σ(每一棵树中叶子节点的数量-1)

具体的实现细节可以看代码

CODE:

#include
#include
#include
#include
#include
#include
#include
#define M 100861
using namespace std;
int n,tot,cnt,top;
int edge[M],to[M],nex[M],head[M];
int dfn[M],low[M],sta[M];
int bel[M],belt[M],wt[M];
bool vis[M];
int in[M],out[M];
vector have[M],leaf[M],root[M];
void add(int x,int y)
{to[++tot]=y;nex[tot]=head[x];head[x]=tot;}
void Tarjan(int now)
{
//	printf("now is at %d\n",now);
	dfn[now]=low[now]=++cnt;sta[++top]=now;vis[now]=1;
	for(int i=head[now];i;i=nex[i])
	{
		int v=to[i];
		if(!dfn[v]) {Tarjan(v);low[now]=min(low[now],low[v]);}
		else if(vis[v]) {low[now]=min(low[now],dfn[v]);}
		
	}
	if(dfn[now]==low[now])
	{
		++tot;
		while(sta[top+1]!=now)
		{
			bel[sta[top]]=tot;
			vis[sta[top]]=0;
			have[tot].push_back(sta[top]);//我是用vector存储每一个强连通分量里面的点 
			--top;
		}
	}
}
int find(int x)
{return x==belt[x] ? x:belt[x]=find(belt[x]);}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy) belt[fx]=fy;
}
int main()
{
	scanf("%d",&n);
	
	for(int i=1,x;i<=n;++i)
	{
		scanf("%d",&x);edge[i]=x;
		
		add(i,x);
	}
	tot=0;
	for(int i=n;i;--i) if(!dfn[i]) Tarjan(i);//使用Tarjan来缩点 
	if(tot==1) 
	{//如果缩点之后只存在一个点的话  那么这已经是强连通图了 
		printf("0");
		return 0;
	}
	for(int i=1;i<=tot;++i) belt[i]=i;//我使用并查集来区分每一棵树 
	for(int i=1;i<=n;++i)
	{
		if(bel[i]!=bel[edge[i]])
		{//统计缩完点之后每一个缩点对应的入度以及出度 
			merge(bel[i],bel[edge[i]]);
			in[bel[edge[i]]]++;
			out[bel[i]]++;
		}
	}
	cnt=0;
	int tmp=0;
	for(int i=1;i<=tot;++i)
	{//现在使用vector存储每一棵树的叶子节点以及根节点 
		int fx=find(i);
		if(!wt[fx]) wt[fx]=++cnt;
		if(in[i]==0) root[wt[fx]].push_back(i);
		if(out[i]==0) leaf[wt[fx]].push_back(i); 
	}
	for(int i=1;i<=cnt;++i) tmp+=(int)root[i].size()-1;
	printf("%d\n",cnt+tmp);
	for(int i=1;i<=cnt;++i)
	{
		if(i