F. Upgrading Cities
题意
给你一个n个点m条边的DAG（有向无环图），问有多少个点的可到达的点数+可以被到达的点数>=n-1
做法
由于是有向无环图，我们首先考虑拓扑排序，如果A能够到达B，那么A,B肯定不会同时出现在队列中，所以如果队列中同时存在的点超过两个，这些点肯定都是不能互相到达的，也就是说对答案肯定没有贡献，之后考虑如果队列中只有一个点，那么所有没进队的点肯定都能到达，之后考虑如果队列中恰好有两个点，设两个点分别为A，B，B有一条边指向一个入度为1的点C，那么A肯定不能到达C，所以A到达不了A,B,也就是A不能对答案做贡献，如果没有这种情况，A可以到所有剩下没有进入队列的点。这是处理一个点能到哪些点的情况，对于被哪些点到达的情况，只需要反向建边再跑一边这个过程即可。两遍topo排序之后，看哪些点满足条件即可。
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 3e5+5;
vector<int> G[2][maxn];
int ind[2][maxn],que[maxn],n,m;
int sum[maxn];
void topsort(int pos)
{
int qt = 0;for(int i = 1; i <= n; ++i){
if(ind[pos][i] == 0) que[qt++] = i;}for(int i = 0; i < qt; ++i){
int u = que[i];if(qt-i==1){
sum[u]+=n-qt;}else if(qt-i==2){
int u_2=que[i+1];int flag=0;for(int j=0;j<G[pos][u_2].size();++j) if(ind[pos][G[pos][u_2][j]]==1) flag=1;if(flag==0) sum[u]+=(n-qt);}for(int j=0;j<G[pos][u].size();++j) if(--ind[pos][G[pos][u][j]] == 0) que[qt++] = G[pos][u][j];}return ;
}
int main()
{
scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);G[0][u].push_back(v);ind[0][v]++;G[1][v].push_back(u);ind[1][u]++;}topsort(0);topsort(1);int ans=0;for(int i=1;i<=n;i++) if(sum[i]>=n-2) ++ans;printf("%d\n",ans);return 0;
}