AtCoder ARC #111 : D - Orientation

問題の前提を信じて突っ込んだ感はある。
https://atcoder.jp/contests/arc111/tasks/arc111_d

問題

無向グラフが与えられる。
このグラフの各辺に対し、どちらかの向きを与えたい。
その際、各点vに値C[v]が指定される。これは点vから有効辺をたどって到達できる頂点を示す。

必ず解が存在するような入力が与えられるので、解の例を示せ。

解法

u-vをつなぐ辺があったとき、C[u]とC[v]が異なるなら辺の向きは自明。
残りはC[u]=C[v]となる辺が残るが、C[u]=C[v]ということはこれらの辺は閉路を成すように向きを設定しなければならない。
そのような辺でつながる連結成分に対し、DFS順で向きを設定していけばよい。

int N,M;
int A[202020],B[202020],D[202020];
int C[101];
int E[101][101];
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<101> uf;


void dfs(int cur) {
	int i;
	FOR(i,N) if(C[cur]==C[i]&&E[cur][i]>=0&&D[E[cur][i]]==-1) {
		int x=E[cur][i];
		if(A[x]==cur) D[x]=0;
		else D[x]=1;
		dfs(i);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(D);
	MINUS(E);
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		E[A[i]][B[i]]=i;
		E[B[i]][A[i]]=i;
	}
	FOR(i,N) cin>>C[i];
	FOR(i,M) {
		if(C[A[i]]>C[B[i]]) D[i]=0;
		if(C[A[i]]<C[B[i]]) D[i]=1;
		if(C[A[i]]==C[B[i]]) uf(A[i],B[i]);
	}
	
	FOR(i,N) if(uf[i]==i) dfs(i);
	
	
	FOR(i,M) {
		if(D[i]==0) cout<<"->"<<endl;
		else cout<<"<-"<<endl;
	}
	
}

まとめ

これもすんなり解けてよかった。