USACO JAN08 Silver Cow Contest 奶牛的比赛
由题意可知，当一头牛能胜过的牛与能输给的牛的和为全部的牛时，该牛的名次可知。
根据关系构图，首先每头牛为一个顶点。如果i强于j，从i到j建立有向边，构造出图G1。根据G1构造G1的逆图G2。
以图中的每个顶点i为起点，遍历图G1,G2。记从顶点i开始遍历G1到的顶点集合为A，从顶点i开始遍历G2到的顶点集合为B。如果A∪B=V (V为全部顶点集)，则这个牛的名次可知。
/*
ID: cmykrgb1
PROG: contest
LANG: C++
*/
#include <iostream>
#define MAX 101
using namespace std;
class list
{
public:
list *next;
int p;
list(int &tp)
{
p=tp;
next=0;
}
};
class tadjl
{
public:
list *first,*last;
tadjl()
{
first=last=0;
}
void ins(int p)
{
if (first)
last=last->next=new list(p);
else
first=last=new list(p);
}
};
tadjl adjl[MAX],rdjl[MAX];
int N,M,cnt,Ans;
bool vis[MAX];
void init()
{
int i,a,b;
freopen("contest.in","r",stdin);
freopen("contest.out","w",stdout);
cin >> N >> M;
for (i=0;i<M;i++)
{
cin >> a >> b;
adjl[a].ins(b);
rdjl[b].ins(a);
}
}
void dfs(int i,tadjl *L)
{
int j;
list *k;
cnt++;
vis[i]=true;
for (k=L[i].first;k;k=k->next)
{
j=k->p;
if (!vis[j])
{
dfs(j,L);
}
}
}
void solve()
{
int i;
for (i=1;i<=N;i++)
{
memset(vis,0,sizeof(vis));
cnt=0;
dfs(i,adjl);
dfs(i,rdjl);
if (cnt==N+1)
Ans++;
}
}
int main()
{
init();
solve();
cout << Ans << endl;
return 0;
}
上次修改时间 2017-02-03