【TYVJ1936】【Clover杯NOIP模拟赛IV】太空战队

【问题描述】　　

　　在社会经济高速发展的今天，借助高科技手段，组建太空战队的愿望就快实现了。

　　战队属下有N个航天员。作为空军选拔上来的佼佼者，每个航天员都有与生俱来的骄傲——他们每个人都认为自己是最强的或者是第二强的。这样，如何分组就成了司令官的难题了。司令官分组的方法是这样的：
　　步骤1:任意选择一个未被分组的航天员，记为当前航天员.
　　步骤2:把当前航天员分入一个新的组.
　　步骤3:如果当前航天员心目中最强的那个航天员（记为Q航天员）还没有被分组，那么把Q航天员分入当前航天员所在组，并把Q航天员作为当前航天员并重复步骤3；如果Q航天员已经被分组，那么重复步骤1，直至所有航天员都被分入了某个组。
司令官想请你帮忙计算：按上面的分组方式，最多/最少能分成几个组。

　　N<= 100000

【分析】

　　这题比较简单。依照题给的边连成一个有向图(注意，不一定连通)，然后强联通分量缩点染色，最多能分的组数就是缩点后的点数，最少能分的组就是缩点后入度为0的点数。

　　注意自环。

　　求强联通分量我用的是tarjan的算法，这个算法简洁，应用范围广，效率高，值得推荐。

【代码】

　　

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int d[],low[],dfn[],edge[],color[],q[];

bool p[],instack[];

int n,Count,ct,qt;

void dfs(int x)

{

    p[x] = true;

    dfn[x] = low[x] = ++Count;

    q[++qt] = x;

    instack[x] = true;

    int v = edge[x];

    if (!p[v])

    {

        dfs(v);

        low[x] = min(low[x],low[v]);

    }else

    if (instack[v] && v != x)

        low[x] = min(low[x],dfn[v]);

    if (low[x] == dfn[x])

    {

        int j;

        ct ++;

        do

        {

            j = q[qt];

            instack[j] = false;

            color[j] = ct;

            qt--;

        }while (j != x);

    }

}

int main()

{

    scanf("%d",&n);

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

        scanf("%d",&edge[i]);

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

        if (!p[i])

            dfs(i);

    int ans1 = ct;

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

        if (color[i] != color[edge[i]])

            d[color[edge[i]]] ++;

    int ans2 = ;

    for (int i = ;i <= ct;i ++)

        if (!d[i])

            ans2 ++;

    printf("%d %d",ans1,ans2);

}