Central Europe Regional Contest 2012 Problem J: Conservation

时间:2024-09-13 00:07:08

题目不难,感觉像是一个拓扑排序,要用双端队列来维护;

要注意细节,不然WA到死  = =!

 #include<cstdio>
#include<cstring>
#include<vector>
#define maxn 100005
using namespace std; int q[*maxn],count[][maxn],tail,head,n,m,in[maxn];
vector<int>ve[maxn]; int solve(int lab)
{
head=tail=n;
int cnt=,cc=,f=lab;
for(int i=;i<=n;i++)
if(count[-lab][i]==&&in[i]==lab){q[tail++]=i;cnt++;}
if(cnt==)return -;
for(int i=;i<=n;i++)
if(count[-lab][i]==&&in[i]!=lab){q[tail++]=i;}
while(head<tail)
{
int v=q[head++];
if(in[v]!=f){f=in[v];cc++;}
int l=ve[v].size();
for(int i=;i<l;i++)
{
count[-lab][ve[v][i]]--;
if(count[-lab][ve[v][i]]==)
{
if(in[v]==in[ve[v][i]])
q[--head]=ve[v][i];
else q[tail++]=ve[v][i];
}
}
}
return cc;
} int main()
{
int t,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)ve[i].clear();
memset(count,,sizeof count);
for(int i=;i<=n;i++)scanf("%d",&in[i]);
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
ve[x].push_back(y);
count[][y]++;
count[][y]++;
}
x=solve();
y=solve();
if(x<||y<)printf("%d\n",max(x,y));
else printf("%d\n",min(x,y));
}
return ;
}