/**
problem: http://poj.org/problem?id=2186 当出度为0的点(可能是缩点后的点)只有一个时就存在被所有牛崇拜的牛
因为如果存在有两个及以上出度为0的点的话,他们不会互相崇拜所以不存在被所有牛崇拜的牛
牛的个数即该出度为0点(由环缩点而来)有多少牛
**/
#include<stdio.h>
#include<stack>
#include<algorithm>
using namespace std; class Graphics{
const static int MAXN = ;
const static int MAXM = ;
private:
struct Edge{
int to, next;
}edge[MAXM];
struct Point{
int dfn, low, color;
}point[MAXN];
int sign, dfnNum, colorNum, sumOfPoint, first[MAXN], count[MAXN];
bool vis[MAXN];
stack<int> stk;
void tarjan(int u){
point[u].dfn = ++dfnNum;
point[u].low = dfnNum;
vis[u] = true;
stk.push(u);
for(int i = first[u]; i != -; i = edge[i].next){
int to = edge[i].to;
if(!point[to].dfn){
tarjan(to);
point[u].low = min(point[to].low, point[u].low);
}else if(vis[to]){
point[u].low = min(point[to].dfn, point[u].low);
}
}
if(point[u].dfn == point[u].low){
vis[u] = false;
point[u].color = ++colorNum;
count[colorNum] ++;
while(stk.top() != u){
vis[stk.top()] = false;
point[stk.top()].color = colorNum;
count[colorNum] ++;
stk.pop();
}
stk.pop();
}
}
public:
void clear(int n){
sign = dfnNum = colorNum = ;
for(int i = ; i <= n; i ++){
first[i] = -;
vis[i] = ;
count[i] = ;
}
sumOfPoint = n;
while(!stk.empty()) stk.pop();
}
void addEdgeOneWay(int u, int v){
edge[sign].to = v;
edge[sign].next = first[u];
first[u] = sign ++;
}
void addEdgeTwoWay(int u, int v){
addEdgeOneWay(u, v);
addEdgeOneWay(v, u);
}
void tarjanAllPoint(){
for(int i = ; i <= sumOfPoint; i ++){
if(!point[i].dfn)
tarjan(i);
}
}
int getAns(){
int ans = , ans2 = ;
int *outdegree = new int[sumOfPoint+];
for(int i = ; i <= sumOfPoint; i ++){
outdegree[i] = ;
}
tarjanAllPoint();
for(int i = ; i <= sumOfPoint; i ++){
for(int j = first[i]; j != -; j = edge[j].next){
int to = edge[j].to;
if(point[to].color != point[i].color){
outdegree[point[i].color] ++;
}
}
}
for(int i = ; i <= colorNum; i ++){
if(!outdegree[i]){
ans ++;
ans2 = count[i];
}
}
delete []outdegree;
if(ans == ){
return ans2;
}else{
return ;
}
}
}graph; int main(){
int n, m;
scanf("%d%d", &n, &m);
graph.clear(n);
while(m --){
int a, b;
scanf("%d%d", &a, &b);
graph.addEdgeOneWay(a, b);
}
printf("%d\n", graph.getAns());
return ;
}
05-11 22:43