POJ 3660 Cow Contest （dfs）

Cow Contest

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11129		Accepted: 6183

Description

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

Output

* Line 1: A single integer representing the number of cows whose ranks can be determined
　

Sample Input

Sample Output

Source

USACO 2008 January Silver

【分析】给你一些关系，例如输入u,v，表示u排在v的前面，然后问你有哪些人的排名是可以确定的。

首先可以看出这些关系最终组成了一个有向无环图，也就是说输入u,v,u-->v;我们对于每个人查找确定排在他前面的人的个数和确定排在他后面的人的个数，

如果加起来连同他自己==n，那么说明这个人的排名确定了，那么怎么确定有多少人一定排在他前面呢？我们建两个图，一个顺序，一个逆序，然后分开找就行了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 10000000
#define mod 10000
typedef long long ll;
using namespace std;
const int N=605;
const int M=50000;
int power(int a,int b,int c){int ans=1;while(b){if(b%2==1){ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;}
int in[N],vis[N];
int n,m,k;
vector<int>vec[N],edg[N];
int dfs1(int x)
{
    vis[x]=1;
    int ans=1;
    for(int i=0;i<vec[x].size();i++){
        int v=vec[x][i];
        if(!vis[v])ans+=dfs1(v);
    }
    return ans;
}
int dfs2(int x)
{
    int ans=1;
    vis[x]=1;
    for(int i=0;i<edg[x].size();i++){
        int v=edg[x][i];
        if(!vis[v])ans+=dfs2(v);
    }
    return ans;
}
int main()
{
    int u,v,ans=0;;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        edg[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        int ret1=dfs1(i);
        memset(vis,0,sizeof vis);
        int ret2=dfs2(i);
        //printf("!!%d %d
",ret1,ret2);
        if(ret1+ret2==n+1)ans++;
    }
    printf("%d
",ans);
    return 0;
}