链式前向星
struct edge{ int next;//第i条边同起点的下一条边的存储位置 int to;//第i条边的终点 int w;//边权值 }; void add(int u, int v, int w){ edge[cnt].w = w; edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; }拓扑排序
struct node{ int next; int to; int w; }edge[25005]; int head[25005],cnt=0; void add(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } int indegree[200005],a[200005],n,m,s; void toposort(){ queue<int>q; for(int i=1;i<=n;i++) if(indegree[i]==0)//第i个顶点的入度为0 q.push(i); while(!q.empty()){ int t=q.front();//第i个顶点拿出来 q.pop(); a[s++]=t;//j记录路径 for(int i=head[t];~i;i=edge[i].next){ indegree[edge[i].to]--; if(indegree[edge[i].to]==0) q.push(edge[i].to); } } } int main() { memset(indegree,0,sizeof(indegree)); memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); int t,x,y; for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); add(x,y); indegree[y]++; } s=0; toposort(); for(int i=0;i<s;i++) printf("%d ",a[i]); return 0; }题目： 给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。N,M≤30000。
题解：看到有向无环图，想到拓扑排序
#include<bits/stdc++.h> using namespace std; const int maxn = 3e4+10; struct Edge{ int next; int to; int w; }edge[maxn]; int head[maxn]; int a[maxn]; int cnt = 0, tot = 0; int n, m; bitset <maxn> s[maxn]; int indegree[maxn]; int copyinde[maxn]; void add(int u, int v){ edge[++cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt; } void toposort(){ queue<int> q; for(int i = 1; i <= n; i++){ if(indegree[i] == 0) q.push(i); } while(!q.empty()){ int t = q.front(); q.pop(); a[++tot] = t; for(int i = head[t]; ~i; i = edge[i].next){ indegree[edge[i].to]--; if(indegree[edge[i].to] == 0) q.push(edge[i].to); } } } int main(){ scanf("%d%d", &n, &m); memset(head, -1, sizeof(head)); int x, y; for(int i = 1; i <= m; i++){ scanf("%d%d", &x, &y); add(x, y); indegree[y]++; // copyinde[y]++; } toposort(); for(int i = tot; i >= 1; i--) { int x = a[i]; s[x][x] = 1; for(int j=head[x]; j; j = edge[j].next) { int to=edge[j].to; s[x] |= s[to]; } } for(int i = 1; i <= n; i++) printf("%d\n",s[i].count()); return 0; }