POI SZP

POI   SZP

POI   SZP

POI   SZP

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;
}
上一篇:黑马程序员——JAVA基础之常用DOS命令和环境变量的配置


下一篇:TheSeventhWeekJavaText