题目描述

上帝手中有着n种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。
由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2^n)级别的算法。虽然上帝拥有无限多的时间，但是他也是个急性子。你需要帮助上帝解决这个问题。

---

思路

将相互影响的点连一条单向边，将入度为0的点加入队列中并将其标记，然后将其指向的点(x)标记起来，如果x本来没有被标记，那么ans++，然后将全部x连接的点入度–，如果这个被减的点入度为0且没有被标记，那么将这个点入队 然后枚举每一个点，如果这个点没有被标记，则该点肯定在一个环中。我们可以用搜索(while)来求出该环中有多少个点(tot)， ans += tot / 2

---

#include 
#include 
using namespace std;
#define maxn 1000005
struct edge
{
    int to, next;
}e[maxn];
int ls[maxn], in[maxn], n, ans = 0, a[maxn];
bool f[maxn];
int find(int x)
{
    int tot = 0;
    int now = x;
    while (!f[x])
    {
        tot++;
        f[x] = 1;
        x = a[x];
    }
    return tot;
}
int bfs()
{
    queue t;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0)
            t.push(i);
    while (!t.empty())
    {
        int now = t.front();
        t.pop();
        f[now] = 1;
        for (int i = ls[now]; i; i = e[i].next)
        {
            if (f[e[i].to] == 0)
            {
                f[e[i].to] = 1;
                ans++;
                if (--in[a[e[i].to]] == 0 && f[a[e[i].to]] == 0)
                    t.push(a[e[i].to]);
            }

        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int y;
        scanf("%d", &y);
        a[i] = y;
        e[i] = (edge) {y, ls[i]};
        ls[i] = i;
        in[y]++;
    }
    bfs();
    for (int i = 1; i <= n; i++)
        if (!f[i]) ans += find(i) >> 1;
    printf("%d", ans);
}