Scheme

原题：Scheme

原题大意

给出n个节点，以及和这个节点指向的节点fi，表示从i能够到达fi，问至少需要添加多少条边能够使得原图变为强连通分量，输出边数及添加的边，多解输出任意一组解。

算法分析

每个点的出度都是1，可以知道这个图的每个弱连通分量（取消定向后的连通块）都是一个有向环上挂很多棵有向树，如果只有一个弱连通分量，显然就是环上随便找一个点然后向所有入度为0的点连边，否则先考虑将所有分量连起来，假设有t个分量，对这些分量从0到t-1标号，对于第i个分量，如果第(i+1)%t个分量有入度为0的点，那么从第i个分量的环上任取一个点向第(i+1)%t个分量的任意一个入度为0的点连边，否则连到环上任意一个点，现在所有分量已经连成了一个分量，并且最小化了入度为0的点，接下来只需要任取一个环上的点向所有入度为0的点连边即可。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100005;
int fwd[maxn];  //forword，fwd[a] = b (a到b，a--->b)
int ind[maxn];  //每个点的入度
int vis[maxn]; 
int tot;        //连通分量的个数
int cir[maxn];  //n个点每个点所在的连通分量（1~tot）
int ker[maxn];  //每个连通分量环上的一点，并且此点代表整个连通分量
int lef[maxn];  //每个连通分量被选为连接的点，如果存在入度为0的，那就任选一个入度为0的，否则为环上任意一点
int usd[maxn];  //与lef一起使用，如果该连通分量里，入度里为0的某点，被选来连接相邻的连通分量，则标记已经用过了
void dfs(int u,int la)
{
    if(vis[u])
    {
        if(!cir[u])
        {
            ker[++tot]=u;
            cir[u]=tot;
        }
        return;
    }
    vis[u]=1;
    dfs(fwd[u],u);
    cir[u]=cir[fwd[u]];
}
int cnt,reu[maxn],rev[maxn];
int main()
{
//freopen("input.txt", "r", stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&fwd[i]);
        ind[fwd[i]]++;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i,0);

/*    for(int i = 1; i <= n; i++)
        cout << ker[i] << " ";
    cout << endl;
    for(int i = 1; i <= n; i++)
        cout << cir[i] << " ";
    cout << endl;

*/
    //选择任意一个连通分量上的入度为0的点
    for(int i=1;i<=n;i++)
        if(!ind[i])lef[cir[i]]=i;

    for(int i=1;i<=tot;i++)
    {
        //如果一个连通分量里没有入度为0的点，就连接环上的任意一点
        if(!lef[i])lef[i]=ker[i];
        else usd[lef[i]]=1;
    }

    for(int i=1,j=2;i<=tot;i++,j++)
    {
        if(j>tot)j=1;//除模的意思，i 向 i+1连
        if(ker[i]!=lef[j])//如果只有一个连通分量就跳过，否则进行连接操作
        {
            cnt++;
            reu[cnt]=ker[i];
            rev[cnt]=lef[j];
        }
    }
    for(int i=1;i<=n;i++)
        if(!ind[i] && !usd[i])//入度为0，并且之前没有被选为用于连通分量的连接
        {
            cnt++;
            reu[cnt]=ker[1];
            rev[cnt]=i;
        }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d %d\n",reu[i],rev[i]);

    return 0;
}