不太明白各位大佬的做法,这道题直接连反边,做一遍topo排序不就行了吗?(求解)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
int n, m;
vector<int> vec[N];
int deg[N];
int w[N];
int a[N];
int q[N];
bitset<N> f[N];
void topo()
{
int l = 0, r= -1;
for(int i = 1; i <= n; i ++ )
{
if(!deg[i]) q[ ++ r] = i;
}
while(l <= r)
{
int u = q[l];
f[u][u] = 1;
for(int i = 0; i < vec[u].size(); i ++ )
{
int v = vec[u][i];
f[v] |= f[u];
if(!(--deg[v])) q[ ++ r] = v;
}
l ++;
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
int u, v;
cin >> u >> v;
vec[v].push_back(u);
deg[u] ++;
}
topo();
for(int i = 1; i <= n; i ++ )
cout << f[i].count() << endl;
}