[AT_arc111_d] [ARC111D] Orientation 题解

小清新思维题！

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

注意到有向图形如若干个 SCC 缩点成一个 DAG，显然 SCC 内

c_i

相等，而拓扑序下最大（即没有出度）的 SCC，其

c

值必然是最小的，于是从小到大枚举

c

，对这些

c

相等的点所在的 SCC，内部可以通过一遍 dfs 直接确定边的定向，对这些 SCC 向外连的还没有确定的边，直接连向这个 SCC 自身（保证拓扑序最大），不断模拟即可。

复杂度差不多是

\mathcal{O}(n(n+m))

的。

code

CPP

#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;
}

[AT_arc111_d] [ARC111D] Orientation 题解

文章操作

相关推荐

评论

[AT_arc111_d] [ARC111D] Orientation 题解