法1
对图直接深搜
TLE !!!
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=30010 ;
const int M=2*N;
bool st[N];
int a[N];
int h[N],e[M],ne[M],idx;
int n,m;
void Init(){
memset(h,-1,sizeof h);
}
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
// 返回以u为根的树 的结点的数目 包含u
int dfs(int u){
st[u]=true;
int sum=1;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) {
int s=dfs(j);
sum+=s;
}
}
return sum;
}
int main(){
Init();
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++) {
memset(st,false,sizeof st);
a[i]=dfs(i);
}
for(int i=1;i<=n;i++) cout<<a[i]<<endl;
return 0;
}
法2
对该有向无环图进行拓扑排序得到拓扑序列,再对拓扑序列逆行进行 bitset 或运算
AC !!!
#include <cstring>
#include <bitset>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=30010 ;
const int M=2*N;
bitset <N> f[N];
/*
bitset<N> s 代表s是个01串,长度为N
bitset<N> f[N] 代表f是个二维数组 共N行N列,
每一行是f[i],f[i]是长度为N的01串,在本题中若f[i][j]=1 说明i可以到达j
若 a-->b 且 a-->c
则 a可以到达的点为 a自身 并 b可以到达的点 并 c可以到达的点
即 f[a]|=f[b],f[a]|=f[c]
*/
int h[N],e[M],ne[M],idx;
int d[N]; // 入度
int q[N]; // 模拟队列
int n,m;
// 初始化 h --> -1
void Init(){
memset(h,-1,sizeof h);
}
// 两点之间建立联系
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
// 拓扑排序
void topsort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(!d[j]) q[++tt]=j;
}
}
}
int main(){
Init();
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
topsort();
// 拓扑排序后得到拓扑序列: 把一个图变成了一条一维直线
for(int i=n-1;i>=0;i--){ // 下标
int t=q[i]; // 点的编号
f[t][t]=1; // 可以到达自己
for(int j=h[t];j!=-1;j=ne[j]){
int k=e[j]; // 点的编号
f[t]|=f[k];
}
}
for(int i=1;i<=n;i++) cout<<f[i].count()<<endl;
return 0;
}