ACwing164. 可达性统计

    科技2024-03-28  88

    题意:

    求出每个点可以到达的点的个数

    思路:

    就是一个简单的图的暴力,为什么拿出来讲下,是因为看题解的时候看到个东西觉得挺不错的,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; } }
    Processed: 0.012, SQL: 8