直接建反边 拓扑的时候直接统计就行了,不用排完序后再统计,题解都是先排序后统计。
#include <iostream>
#include <bitset>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 3e4 + 5;
struct E{
int next , to;
}edge[N<<1];
int head[N],cnt;
void add(int u ,int to)
{
edge[++cnt].next = head[u] ; edge[cnt].to = to ; head[u] = cnt ;
}
int n,m;
int deg[N];
bitset<N> f[N];
queue<int> q;
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i = 1 ; i <= m ; i++ )
{
scanf("%d%d",&x,&y);
add(y,x);
deg[x]++;
}
for(int i = 1 ; i <= n ; i++ )
if(!deg[i])
{
q.push(i);
f[i][i] = 1;
}
while(!q.empty())
{
int x = q.front() ; q.pop();
for(int i = head[x] ; i ; i = edge[i].next )
{
int v = edge[i].to;
f[v] |= f[x];
if(--deg[v]==0) q.push(v) , f[v][v] = 1;
}
}
for(int i = 1 ; i <= n ; i++ )
cout << f[i].count() << endl;
return 0;
}
终于找到一个跟我一样建反边的了,呜呜呜
标题写错了吧,acwing鸭
感谢提醒 已修改