补题：HNU暑期训练第二场H（UVALive-7822）——Explosion at Cafebazaar

我会带着你远行 2022-05-17 00:46 195阅读 0赞

题目链接：  
[UVALive-7822][]

题目大意：给你一个n个点，m条边得有向图，每个点有两种状态：发送状态（给ta所有直接指向的点发送它所有的数据，发送完毕后清空自己的数据），接收状态（接收所有直接指向自己的点的数据和）。初始状态是，所有点都处于发送状态，其中某个点i有1 bit数据，接着发送状态完毕后转换为接收状态，不断交替。  
问有多个点当把初始数据放在它上面时，随着时间的进行，图中某点或多个点的数据会不断增大？

解题思路：从题目可以知道，要使得图中数据不断增大，必然之前的数据不能被清空了，所有图必须要有环。有环还不够，因为接收和发送状态是交替进行，刚好可以在环上循环。因此如果环上有小环，或者有边指向环，那么这个环肯定会随时间进行，数据不断增大  
因此，我们只需要考虑两种情况：第一：强连通分量中不止一个环；第二：有边指向该强连通分量。当然我们还要考虑，如果某个强连通分量能够引起数据不断增大，那么强连通分量所有的父节点都可以引起数据不断增大，导致阻塞了整个图！！！

先用tarjan算法求出图中所有强连通分量；接着再次遍历一遍所有顶点的边，是否有顶点指向了两次所在强连通分量的顶点（只有就可以确认强连通是否存在多个环），是的话，该强连通分量所有点都可以造成数据不断增大。或者这条边把两个强连通分量（且点数都大于1）连接起来了，那么出边的那个强连通分量的顶点也是会引起。

最后需要反向dfs一遍图，以便把会引起数据增大的强连通分量的所有父节点纳入答案

AC代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    
    const int MAXN =50010;
    int dfn[MAXN],low[MAXN],vis[MAXN],stack[MAXN];
    int f[MAXN],num[MAXN],is_exp[MAXN],vis2[MAXN];
    vector<int> g[MAXN],g2[MAXN];
    int n,m,cnt,top,ans,_time;
    
    void tarjan(int u){
        dfn[u]=low[u]=++_time;
        vis[u]=1;
        stack[++top]=u;
        for(int j=0; j<g[u].size(); ++j){
            int v=g[u][j];
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }else if(vis[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
    
        if(dfn[u]==low[u]){
            cnt++;
            int t;
            do{
                t=stack[top];
                vis[t]=0;
                f[t]=cnt;
                num[cnt]++;
                top--;
            }while(t!=u);
        }
    }
    
    void dfs(int u){
        vis2[u]=1;
        for(int j=0; j<g2[u].size(); ++j){
            int v=g2[u][j];
            if(f[u]!=f[v]){
                if(is_exp[f[u]]) is_exp[f[v]]=1;
            }
            if(!vis2[v]){
                dfs(v);
            }
        }
    }
    void solve(){
        for(int u=1; u<=n; ++u){
            int out=0;
            for(int j=0; j<g[u].size(); ++j){
                int v=g[u][j];
                if(f[u]==f[v]) out++;
                else if(num[f[u]]>1&&num[f[v]]>1) is_exp[f[u]]=1;
            }
            if(out>1) is_exp[f[u]]=1;
        }
        for(int i=1; i<=n; ++i){
            if(is_exp[f[i]]&&!vis2[i]) dfs(i);
        }
    }
    void init(){
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(vis,0,sizeof(vis));
        memset(vis2,0,sizeof(vis2));
        memset(stack,0,sizeof(stack));
        memset(num,0,sizeof(num));
        memset(is_exp,0,sizeof(is_exp));
        memset(f,0,sizeof(f));
        for(int i=0; i<MAXN; ++i) {
            g[i].clear();
            g2[i].clear();
        }
        cnt=top=ans=_time=0;
    }
    
    int main(){
        while(scanf("%d%d",&n,&m)&&(n||m)){
            init();
            for(int i=0; i<m; ++i){
                int u,v;
                scanf("%d%d",&u,&v);
                g[u].push_back(v);
                g2[v].push_back(u);
            }
            for(int i=1; i<=n; ++i){
                if(!dfn[i]) tarjan(i);
            }
        /*  for(int i=1; i<=n; ++i){
                cout<<f[i]<<endl;
            }*/
            solve();
            for(int i=1; i<=cnt; ++i){
                //cout<<is_exp[i]<<endl;
                if(is_exp[i]) ans+=num[i];
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[UVALive-7822]: https://cn.vjudge.net/problem/UVALive-7822