也不一定就要topsort,单单记忆化搜索就可以做到了.
定义f[u]:u能到达的点集
枚举每个点,如果f[u]为空(u一定能到达u,而f[u]为空则说明u未被遍历过),遍历u:
标记u能到达u
对于u能访问到的每个点v:
v未被访问:遍历v
//此时f[v]已知了
因为v能到达的点u一定也能到达,所以令u能到达的点集并上v能到达的点集(f[u]|=f[v])
但点数较多,无法直接用整型变量存储,需要用bitset(bitset是一种STL容器,表示一些为0或1的二进制位,单次操作时间复杂度为$O(n/w)$,w为计算机字长(一般为32或64)
算法时间复杂度$O((n+m)*\frac{n}{w})=O(\frac{n(n+m)}{w})$,空间复杂度$O(\frac{n^2}{w})$.
//Wan Hong 2.2
//notebook
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<bitset>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll x=0,f=1;
char c;
do
{
c=getchar();
if(c=='-')f=-1;
}while(c<'0'||c>'9');
do
{
x=x*10+c-'0';
c=getchar();
}while(c>='0'&&c<='9');
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
/**********/
#define MAXN 30011
std::bitset<MAXN>f[MAXN];
struct Edge
{
ll v,nxt;
}e[MAXN];
ll cnt=0,last[MAXN];
void adde(ll u,ll v)
{
++cnt;
e[cnt].v=v;
e[cnt].nxt=last[u];last[u]=cnt;
}
void dfs(ll u)//遍历u
{
f[u][u]=1;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(!f[v].any())dfs(v);
f[u]|=f[v];
}
}
int main()
{
ll n=read(),m=read();
for(ll i=1;i<=m;++i)
{
ll u=read(),v=read();
adde(u,v);
}
for(ll i=1;i<=n;++i)
{
if(!f[i].any())dfs(i);//u未被遍历过则遍历
printf("%lld\n",f[i].count());
}
return 0;
}
点太多的情况下,直接这样dfs不知道会不会炸栈…
递归次数最坏情况下与$n$同阶,即使不额外开栈,200k递归没啥问题
资瓷大佬
Orz