题解
拓扑排序即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
typedef long long ll;
typedef struct{
int v,_next;
}Edge;
Edge edge[200005];
int cnt=0,at[100005],ru[100005]={0},V,E,ans[100005]={0};
int q[100005],f=0,r=0;
void addedge(int _u,int _v){
edge[cnt].v=_v,
ru[_v]++,
edge[cnt]._next=at[_u],
at[_u]=cnt++;
}
void init(){
scanf("%d%d",&V,&E);
int i,j,u,v;
memset(at,-1,sizeof(at));
for(i=0;i<E;i++)
scanf("%d%d",&u,&v),
addedge(u-1,v-1);
}
void solve(){
int Ans=0;
for(int i=0;i<V;i++)
if(!ru[i]&&at[i]!=-1)
ans[i]=1,q[r++]=i;
while(r-f){
int h=q[f++],i,_v;
for(i=at[h];i!=-1;i=edge[i]._next){
_v=edge[i].v;
ru[_v]--;
ans[_v]+=ans[h];
if(!ru[_v])
q[r++]=_v;
}
}
for(int i=0;i<V;i++)
if(at[i]==-1)
Ans+=ans[i];
printf("%d\n",Ans);
}
int main(){
init();
solve();
return 0;
}