转换为邻接矩阵，题目要求的就很明了了，不能直接用bool或者int存，要用bitset，（支持位运算），但是空间不能直接开成maxn*maxn,会爆空间。
把原图分成两半做，开maxn*(maxn/2)就行了。
上代码。
1 #include<iostream> 2 #include<bitset> 3 #include<cstring> 4 #include<vector> 5 #define maxn 60005 6 #define maxm 100005 7 using namespace std; 8 bitset<maxn/2>vis[maxn]; 9 int degi[maxn]; 10 bool had[maxn]; 11 int n,m,u,v,ans,mid; 12 bool flg; 13 int head[maxn],cnt; 14 struct EDGE{ 15 int to,nxt; 16 }edge[maxm]; 17 inline void read(int &x){ 18 x=0;int f=1;char c=getchar(); 19 while(!isdigit(c)){f=c=='-'?-1:1;c=getchar();} 20 while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} 21 x=x*f; 22 } 23 inline void adde(int u,int v){ 24 edge[++cnt].nxt=head[u],head[u]=cnt,edge[cnt].to=v; 25 } 26 inline void dfs(int x){ 27 had[x]=1; 28 if(!flg){//如果当前求得是上一半的图 29 if(x<=mid) vis[x].set(x); 30 } 31 else{ 32 if(x>mid) vis[x].set(x-mid); 33 } 34 for(register int i=head[x];i;i=edge[i].nxt){ 35 int t=edge[i].to; 36 if(!had[t]) dfs(t); 37 vis[x]|=vis[t]; 38 } 39 } 40 int main(){ 41 freopen("worldline.in","r",stdin); 42 freopen("worldline.out","w",stdout); 43 read(n),read(m); 44 mid=n>>1; 45 for(register int i=1;i<=m;i++){ 46 read(u),read(v); 47 adde(u,v); 48 degi[v]++; 49 } 50 for(register int i=1;i<=n;i++) if(!degi[i]) dfs(i);//找入度为0的点dfs能遍历整张有向无环图 51 for(register int i=1;i<=n;i++) ans+=vis[i].count(),vis[i].reset(); 52 flg=1;//遍历下半张图 53 memset(had,0,sizeof(had)); 54 for(register int i=1;i<=n;i++) if(!degi[i]) dfs(i); 55 for(register int i=1;i<=n;i++) ans+=vis[i].count(); 56 printf("%d",ans-n-m); 57 return 0; 58 }