AtCoder Beginner Contest 306

G - Return to 1

题意

给定一张有向图，从 $1$ 出发，每步从当前位置走向一个相邻的结点。问是否存在一种走法，使得 $10^{10^{100}}$ 步后回到了 $1$。

题解

首先，我们只关心那些能从 $1$ 走到并且能走到 $1$ 的点。令所有包含 $1$ 的回路长度构成的集合为 $L$。令 $G$ 为这些回路长度的 $\gcd$。原问题有解当且仅当 $G|10^{10^{100}}$。（利用exgcd很容易说明）

但寻找所有的回路长度很麻烦。有一个巧妙的做法：我们考虑一棵以 $1$ 为根的有向树，令 $d_i$ 为 $i$ 在树上的深度。那么有这样一个结论：$L$ 中含有一个数不是 $a$ 的倍数当且仅当存在一条边 $(u,v)$ 满足 $d_u+1\not\equiv d_v\pmod a$。

证明：

充分性：考虑反证法，若所有边 $(u,v)$ 均满足 $d_u+1\equiv d_v$，那么在模 $a$ 意义下，一条从 $1$ 出发的回路所经历的 $d$ 一定是 $0\rightarrow 1\rightarrow\cdots\rightarrow a-1\rightarrow 0\rightarrow 1\rightarrow\cdots a-1\rightarrow 0$。它的长度显然是 $a$ 的倍数。

必要性：选择一条边 $(u,v)$ 满足 $d_u+1\not\equiv d_v\pmod a$，选择一个回路，只包含它一次，且其它所有边均有 $d_u+1\equiv d_v\pmod a$。由于树上的所有边都满足 $d_u+1\equiv d_v$，所以这样的回路必然存在，且长度不是 $a$ 的倍数。

所以我们只需要求出所有边 $(u,v)$ 的 $|d_u+1-d_v|$ 的 $\gcd$，它和 $G$ 是相等的。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> G[maxn],rG[maxn];
int d[maxn];
bool vis[maxn];
void dfs(int u)
{
    for(auto v:G[u])
    {
        if(d[v]!=-1) continue;
        d[v]=d[u]+1;
        dfs(v);
    }
}
void rdfs(int u)
{
    vis[u]=1;
    for(auto v:rG[u])
    {
        if(vis[v]) continue;
        rdfs(v);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++) d[i]=-1,vis[i]=0,G[i].clear(),rG[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;cin>>u>>v;
            G[u].push_back(v),rG[v].push_back(u);
        }
        d[1]=0;
        dfs(1);rdfs(1);
        for(int i=1;i<=n;i++)
            if(!vis[i]) d[i]=-1;
        int g=0;
        for(int u=1;u<=n;u++)
        {
            if(d[u]==-1) continue;
            for(auto v:G[u])
            {
                if(d[v]==-1) continue;
                g=__gcd(g,abs(d[u]+1-d[v]));
            }
        }
        if(!g) cout<<"No"<<'\n';
        else
        {
            while(g%2==0) g/=2;
            while(g%5==0) g/=5;
            cout<<(g==1?"Yes":"No")<<'\n';
        }
    }
    return 0;
}