题目描述
按照拓扑排序的逆序求,因为我们要保证在算某一个点的可达点时,其后面的所有点的可达点都要被算出。
#include <iostream>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
const int N=30010,M=2*N;
int h[N],e[M],ne[M],idx;
int d[N];
int cnt;
int top[N];
int n,m;
//每个点所能达到的集合
bitset<N> f[N];
queue<int> q;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void toop()
{
for(int i=1;i<=n;i++)
{
if(d[i]==0) q.push(i);
}
while(q.size())
{
int t=q.front();
top[cnt++]=t;
//cout<<t<<endl;
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
d[j]--;
if(d[j]==0) q.push(j);
}
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
toop();
//按照拓扑排序的逆序求,因为我们要保证在算某一个点的可达点时,其后面的所有点的可达点都要被算出
for(int i=n-1;i>=0;i--)
{
int j=top[i];
//cout<<j<<endl;
f[j][j]=1;
//遍历j所有的邻边
for(int k=h[j];k!=-1;k=ne[k])
{
f[j] |= f[e[k]];
}
}
//一个点能到达点的个数,就是f[i]中1的个数
for(int i=1;i<=n;i++)
{
cout<<f[i].count()<<endl;
}
return 0;
}
二刷,直接对每个点做dfs,果然是过不了的
#include <iostream>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
const int N=30010,M=2*N;
int h[N],e[M],ne[M],idx;
int cnt[N];
int n,m;
int reach[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u,int v)
{
reach[v]=1;
cnt[u]++;
for(int i=h[v];i!=-1;i=ne[i])
{
int j=e[i];
if(!reach[j])
{
dfs(u,j);
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++)
{
memset(reach,0,sizeof reach);
dfs(i,i);
}
for(int i=1;i<=n;i++)
{
cout<<cnt[i]<<endl;
}
return 0;
}
优化:用拓扑排序做,每次对入度为0的点进行dfs(而不是对所有点都要做),最后这个入度为0的点的可达点数,是后面所有点的和,有继承关系,就不需要每个都遍历一遍
拓扑排序的好处是,若一个点u可到达j,则u可以到达j到达的所有点
#include <iostream>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
const int N=30010,M=2*N;
int h[N],e[M],ne[M],idx;
int cnt[N];
int n,m;
int reach[N];
bitset<N> s[N];
int d[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u)
{
reach[u]=1;
s[u][u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!reach[j])
{
dfs(j);
}
s[u]|=s[j];
}
cnt[u]=s[u].count();
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
for(int i=1;i<=n;i++)
{
if(d[i]==0)
{
dfs(i);
}
}
for(int i=1;i<=n;i++)
{
cout<<cnt[i]<<endl;
}
return 0;
}
三刷,此题和拓扑排序联系不大,倒是和传递闭包联系紧密(参考379 捉迷藏
此题的具体思路如下:
1. 求每个点的可达点,用bitset s[i]来表示,其中1的个数为这个点可达的点的个数
2. dfs遍历每个入度为0的点u,从u一直做dfs到最后,即可完成u这条路所有点可达点的计算
注意要点:
1. bitset的用法为:
bitset<N> s[N];
- 在做dfs时有两个数组要用,一个是reach数组,标记这个点是否被遍历过,如果遍历过则跳过该点,可知每个点只需要遍历一次。另一个就是bitset数组s[u],每次与u的邻点j做按位或
有一个错误做法要记一下,这也是本题要用bitset做法的原因:判重!!!
比如A可以到达B和C,但A可以到达的点的数量 不等于 B可到达的点的数量+C可到达的点的数量!!
因为B和C到达的点可能会有相同的,这就要求用bitset中的或运算判重
#include <iostream>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
const int N=30010;
int e[N],ne[N],h[N],idx;
int n,m;
int cnt[N];
int din[N];
int reach[N];
bitset<N> s[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u)
{
s[u][u]=1;
reach[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!reach[j])
{
dfs(j);
}
s[u]=s[u]|s[j];
}
cnt[u]=s[u].count();
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
din[b]++;
}
for(int i=1;i<=n;i++)
{
if(din[i]==0)
{
dfs(i);
}
}
for(int i=1;i<=n;i++)
{
cout<<cnt[i]<<endl;
}
return 0;
}