题意:
求出每个点可以到达的点的个数
思路:
就是一个简单的图的暴力,为什么拿出来讲下,是因为看题解的时候看到个东西觉得挺不错的,bitset STL里的一个东西,我们在统计可到达点时可能会有很多,所以可以借助biset里面是以二进制存储的,f[i][j]的含义是指d点i和点j之间可不可以到达,通过f[i].count()就可以统计出他的可到达点的数量。
AC代码:
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int maxn
=1e6+10;
typedef pair
<ll
,int> PLI
;
bitset
<30010>f
[30010];
int head
[maxn
],ans
[maxn
],vis
[maxn
];
int n
,m
,cnt
;
struct node
{
int nxt
,v
;
}edge
[maxn
];
void add(int u
,int v
) {
edge
[++cnt
].v
= v
;
edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
;
}
void dfs(int u
) {
f
[u
][u
] = 1;
for(int i
=head
[u
];i
;i
= edge
[i
].nxt
) {
int v
= edge
[i
].v
;
if(!vis
[v
]) dfs(v
);
vis
[v
] = 1;
f
[u
]|=f
[v
];
}
}
int main()
{
cin
>>n
>>m
;
for(int i
=1;i
<=m
;i
++) {
int u
,v
;
cin
>>u
>>v
;
add(u
,v
);
}
for(int i
=1;i
<=n
;i
++) {
if(!vis
[i
]) dfs(i
);
cout
<<f
[i
].count()<<endl
;
}
}
转载请注明原文地址:https://blackberry.8miu.com/read-30134.html