[AT_arc111_d] [ARC111D] Orientation 题解

aeiouaoeiu · 2025-11-10 21:59:01 · 题解

小清新思维题！

题目加粗了有解条件，这是一个关键信息。

注意到有向图形如若干个 SCC 缩点成一个 DAG，显然 SCC 内 c_i 相等，而拓扑序下最大（即没有出度）的 SCC，其 c 值必然是最小的，于是从小到大枚举 c，对这些 c 相等的点所在的 SCC，内部可以通过一遍 dfs 直接确定边的定向，对这些 SCC 向外连的还没有确定的边，直接连向这个 SCC 自身（保证拓扑序最大），不断模拟即可。

复杂度差不多是 \mathcal{O}(n(n+m)) 的。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=107,ee=1e18,p=1e9+7;
struct Edge{ll v,id;};
ll n,m,c[maxn],ans[maxn*maxn],vis[maxn],col[maxn];
vector<Edge> edge[maxn];
vector<ll> vec;
void dfs(ll u){
    if(vis[u]) return;
    ll v,id,tid;
    vis[u]=1;
    for(auto x:edge[u]){
        v=x.v,id=x.id,tid=abs(id);
        if(!ans[tid]){
            if(col[v]){
                if(id>0) ans[tid]=1;
                else ans[tid]=-1;
                dfs(v);
            }else if(id>0) ans[tid]=-1;
            else ans[tid]=1;
        }
    }
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(ll i=1,u,v;i<=m;i++){
        cin>>u>>v;
        edge[u].pb(Edge{v,i}),edge[v].pb(Edge{u,-i});
    }
    for(ll i=1;i<=n;i++) cin>>c[i];
    for(ll t=1;t<=n;t++){
        for(ll i=1;i<=n;i++) vis[i]=col[i]=0;
        for(ll i=1;i<=n;i++)if(c[i]==t) vec.pb(i),col[i]=1;
        for(auto x:vec)if(!vis[x]) dfs(x);
    }
    for(ll i=1;i<=m;i++){
        if(ans[i]>0) cout<<"->\n";
        else cout<<"<-\n";
    }
    return 0;
}

::::