POI SZP

贪心：

初始所有点为白色，对于点i，若a[i]为白色则将其染成与i不同的颜色。

证明：若点i确定为白色，a[i]染白色也只能提供一个黑点，故a[i]染黑色不会差；若所有指向i的点均为黑色，则i只能是白色。

使用拓扑排序实现，一开始将无入度的点入队，最后剩下的环从任意处切开即可。

环上的情况可以分环为奇数，偶数通过讨论得到个数是对的。

SAC大佬%%%orz，提供链接：http://www.cnblogs.com/NaVi-Awson/

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 queue<int>Q;

 int n,m;

 int dist[],a[],ans=;

 bool vis[],c[];

 int in[];

 int main()

 {int i,j;

 //freopen("szp.in","r",stdin);

 //freopen("szp.out","w",stdout);

     cin>>n;

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

     {

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

         in[a[i]]++;

     }

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

       if (!in[i]) Q.push(i);

      while (!Q.empty())

      {

         int u=Q.front();

           Q.pop();

           vis[u]=;

            if (c[u])

            {

              in[a[u]]--;

               if (!c[a[u]]) Q.push(a[u]);

            }

            else

            {

               if (!c[a[u]]) ans++,c[a[u]]=,Q.push(a[u]);

            }

      }

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

       if (!vis[i])

       {

             vis[i]=;

             j=i;

              while (!vis[a[j]])

              {

               if (!c[a[j]]&&!c[j]) ans++,c[a[j]]=;

               j=a[j];vis[j]=;

             }

       }

     cout<<ans;

 }

巴特西

POI SZP

最新文章

热门文章