hdu7050 /2021“MINIEYE杯”中国大学生算法设计超级联赛（7） 1007 Link with Limit

https://acm.hdu.edu.cn/showproblem.php?pid=7050

题意相当于问n个点n条边的有向图（可能有自环），是否所有的环的平均值相等

用tarjan找环效果不甚理想，还是std的拓扑排序妙

#include<bits/stdc++.h>

using namespace std;

#define N 100001

int to[N];

int dfn[N],low[N],id;
int st[N],top;

bool in[N];

double last,now;
int sum;

const double eps=1e-8;

bool equal(double a,double b)
{
    return fabs(a-b)<eps;
}

void tarjan(int u)
{
    low[u]=dfn[u]=++id;
    st[++top]=u;
    in[u]=true;
    int t=to[u];
    if(!dfn[t])
    {
        tarjan(t);
        low[u]=min(low[u],low[t]);
    }
    else if(in[t]) low[u]=min(low[u],dfn[t]);
    if(low[u]==dfn[u])
    {
        if(st[top]==u)
        {
            in[u]=false;
            top--;
            return;
        }
        while(st[top]!=u) 
        {
            in[st[top]]=false;
            now+=st[top--];
            sum++;
        }
        now+=st[top--];
        sum++;    
        in[u]=false;
    }
}             

int main()
{
    //freopen("input.txt","r",stdin); 
    //freopen("my.txt","w",stdout);
    int T,n;
    int self,who;
    bool tag;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i) 
        {
            dfn[i]=0;    
            in[i]=false;
        }
        id=0;
        self=0;
        for(int i=1;i<=n;++i) 
        {
            scanf("%d",&to[i]);    
            if(to[i]==i) 
            {
                ++self;
                who=i;
            }
        }
        if(self>1)
        {
            printf("NO
");
            continue;
        }
        last=-1;
        if(self==1)
        {
            last=who;
            dfn[who]=1;
        }
        tag=true;
        for(int i=1;i<=n && tag;++i)
        {
            if(dfn[i]) continue;
            now=0;
            top=sum=0;            
            tarjan(i);
            if(!sum) continue;
            now/=sum;
            if(!equal(now,last) && !equal(last,-1)) tag=false;
            last=now;
        }
        if(tag) printf("YES
");
        else printf("NO
");
    }
}

#include <stdio.h>
#include <queue>
#define MN 100000
typedef long long ll;

int n,a[MN+5],din[MN+5];

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        din[i] = 0;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        din[a[i]]++;
    }
    std::queue<int> Q;
    for(int i=1;i<=n;i++){
        if(din[i]==0) Q.push(i);
    }
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        din[a[u]]--;
        if(din[a[u]]==0){
            Q.push(a[u]);
        }
    }
    ll p=-1,q=-1;
    for(int i=1;i<=n;i++){
        if(din[i]==0) continue;
        ll tp=0,tq=0;
        for(;din[i];i=a[i]){
            tp += i;
            tq++;
            din[i] = 0;
        }
        if(p==-1){
            p = tp;
            q = tq;
        }else{
            if(p*tq!=q*tp){
                puts("NO");
                return;
            }
        }
    }
    puts("YES");
    return;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
}