补题：HNU暑期训练第二场L-Skeletons

偏执的太偏执、 2022-05-18 09:04 132阅读 0赞

题目链接  
[Skelectons][]

题目大意：在一个n个点，m条边，每个点上都有一个炸弹人，炸弹人可以任意选一个点去炸，但是每个点只能被一个炸弹人选择。问给定有向图是否可以在一个正整数时间里刚好把所有点炸毁。

解题思路：刚开始在看到这题时，因为只要图是一个强连通图就行，后面发现不对。  
我们需要保障每个环之间的节点数的gcd为1（因为只有只样我们才可以利用环节点数差的达到我们想要的结果），才可能符合炸弹人任意选择一个节点作为目标节点去炸的要求  
所以，首先我们需要判断图是否连通，不连通肯定不行  
其次我们求出每个环的节点数，然后依次gcd，看最终ans是否是1

那么问题来了？  
如何求出每个环的节点数？这里采取两次dfs求各点深度，一次正向dfs，一次反向建边，然后再次dfs,这样对于某条边，我们就可以求出其所在环的总节点数=两个端点（这里是指边的起点，因为反向建边了）深度和 - 1

AC代码如下：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    const int MAXN = 50007;
    const int MAXM = 1e5+7;
    
    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    struct edge{
        int v;
        int next;
    }E[MAXM],E2[MAXM];
    
    int head[MAXM],head2[MAXM],deep[MAXN],deep2[MAXN];
    int n,m,cnt,ans;
    
    void addedge(int u,int v){
        E[++cnt].v=v; E[cnt].next=head[u]; head[u]=cnt;
        E2[cnt].v=u; E2[cnt].next=head2[v]; head2[v]=cnt;
    }
    
    void dfs(int u){
        for(int i=head[u]; i!=-1; i=E[i].next){
            int v=E[i].v;
            if(!deep[v]){
                deep[v]=deep[u]+1;
                dfs(v);
            }
        }
    }
    
    void dfs2(int u){
        for(int i=head2[u]; i!=-1; i=E2[i].next){
            int v=E2[i].v;
            if(!deep2[v]){
                deep2[v]=deep2[u]+1;
                dfs2(v);
            }
        }
    }
    
    void init(){
        memset(head,-1,sizeof(head));
        memset(head2,-1,sizeof(head2));
        memset(deep,0,sizeof(deep));
        memset(deep2,0,sizeof(deep2));
        cnt=ans=0;
    }
    
    int main(){
        while(scanf("%d%d",&n,&m)&&(n||m)){
            init();
            for(int i=0; i<m; ++i){
                int x,y;
                scanf("%d%d",&x,&y);
                addedge(x,y);
            }
            deep[1]=deep2[1] =1;
            dfs(1);
            dfs2(1);
            for(int i=1; i<=n; ++i){
                if(deep[i]==0||deep2[i]==0){
                    ans=-1;
                //  cout<<"233"<<endl;
                    break;
                }
            }
        /*  for(int i=1; i<=n; ++i){
                cout<<deep[i]<<" "<<deep2[i]<<endl;
            }*/
            if(ans==0){
                for(int i=1; i<=m; ++i){
                    ans=__gcd(ans,deep[E2[i].v]+deep2[E[i].v]-1);
                }
            }
            if(ans==1) printf("Y\n");
            else printf("N\n");
        }
        return 0;
    }

[Skelectons]: http://acm.hnu.cn/online/?action=problem&type=show&id=14126&courseid=395