【提高组】图的遍历

P1341 无序字母对

欧拉回路板子题。

判断图的联通只要搜完判断点数是否相等即可，因为m组连边必定连m+1个点，前提不重复。也可用并查集。

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Dfor(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
const int M=1330;
int n,m,dis[M][M],s1=M,ans,cnt,h;
string s;
char in[M],a[M];
inline void find(int i){
    For(j,1,150){
        if(dis[i][j]){dis[i][j]--;dis[j][i]--;find(j);}
    }
    a[++ans]=i;
    return;
}
int main(){
    cin>>m;
    For(i,1,m){
        cin>>s;
        dis[s[0]][s[1]]++;dis[s[1]][s[0]]++;
        in[s[0]]++;in[s[1]]++;
    }
    For(i,1,150){
        if(in[i]&1){
            cnt++;
            if(!h) h=i;
        }
    }
    if(!h){
        For(i,0,149){
            if(in[i]){h=i;break;}
        }
    }
    if(cnt&&cnt!=2){cout<<"No Solution";return 0;}
    find(h);
    if(ans<m+1){cout<<"No Solution";return 0;}
    Dfor(i,ans,1){
        printf("%c",a[i]);
    }
    return 0;
}

P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

打了个裸的搜索，40分。

神仙做法不用任何算法在这里：https://www.luogu.org/blog/planetarian/solution-p2921

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int maxn=1e5+5;
int n,nxt[maxn],color[maxn],sucdfn[maxn],dfn[maxn],minc[maxn];
inline void Solve(){
    For(cow,1,n) {
        for(int i=cow,cnt=0;;i=nxt[i],++cnt){
            if(!color[i]){color[i]=cow;dfn[i]=cnt;}
            else if(color[i]==cow){minc[cow]=cnt-dfn[i];sucdfn[cow]=dfn[i];cout<<cnt<<endl;break;}
            else{minc[cow]=minc[color[i]];sucdfn[cow]=cnt+max(sucdfn[color[i]]-dfn[i],0);cout<<sucdfn[cow]+minc[cow]<<endl;break;}
        }
    }
}
int main(){
    cin>>n;
    For(i,1,n) cin>>nxt[i];
    Solve();
    return 0;
}

Tarjan待填坑