题目大意：
给出一个有向无环图，要求对于图中的u,v,t三点，满足u->v,v->t,u->t，经过观察我们发现就是要将图中每一个点连接所有他可以达到的点，最后输出连接的边的数量。
对此我们可以dfs求出每一个点可以到达其他的点边，最后用求出的边数减去原来已经连接的边，其中用bitset优化。
代码送上：
1 #include <cstdio> 2 #include <bitset> 3 #include <iostream> 4 #define For(i, j, k) for(int i = j; i <= k; i++) 5 using namespace std; 6 const int N = 60010, M = 100010; 7 int Begin[N], Next[M], to[M], e; 8 void Add(int u, int v){ 9 to[++e] = v; 10 Next[e] = Begin[u]; 11 Begin[u] = e; 12 } 13 bitset<N/2> G[N];//由于数据太大，要分两次来算 14 int n, m; 15 bool vis[N]; 16 long long Ans; 17 void DFS(int o, bool flag){ 18 vis[o] = true; 19 if(flag && o <= (n >> 1)) G[o][o] = true; 20 else if(!flag && o > (n >> 1)) G[o][o - (n >> 1)] = true; 21 for(int i = Begin[o]; i; i = Next[i]){ 22 int u = to[i]; 23 if(!vis[u]) DFS(u, flag); 24 G[o] |= G[u]; 25 } 26 Ans += G[o].count(); 27 } 28 29 int main(){ 30 scanf("%d%d", &n, &m); 31 For(i, 1, m){ 32 int u, v; 33 scanf("%d%d", &u, &v); 34 Add(u, v); 35 } 36 For(i, 1, n) if(!vis[i]) DFS(i, true);//第一次计算 37 For(i, 1, n) vis[i] = false, G[i].reset(); 38 For(i, 1, n) if(!vis[i]) DFS(i, false);//第二次计算 39 printf("%lld ", Ans - m - n); 40 return 0; 41 }
博主蒟蒻，自己写的代码找不到了，改天写了补上
再次感谢大佬的AC代码