ARC111-D Orientation

これも解けるべきだったなと思う　解法はほぼeditorialそのまま

問題概要

https://atcoder.jp/contests/arc111/tasks/arc111_d

無向グラフが与えられる。次の条件を満たすようにグラフの各辺を向きづけよ。

• 頂点 i から到達可能な頂点数が（自分も含めて）ちょうど C_i 個存在する。

constraints

• 1 ≤ |V| ≤ 100

解法

• 各辺について、両端の頂点をa , bとして、C_a != C_bだったら明らかである。C_a > C_bの時、bから到達できる頂点には必ず a から到達できるため、a -> bの方向に向きづける。

• C_a == C_b の場合。C_aと同じ連結成分内にあって、Cの値が同じ頂点は、「強連結」であることがわかる。ある頂点集合が強連結であるとは、その頂点集合内の任意の2点について、2点を結ぶパスが存在することである。さて、問題は無向頂点集合を向きづけて強連結にすることになったが、これは公式解説にも概要があるが

[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges - Codeforces

ここに詳しく説明されている。これ読んだことあってライブラリまで作ってたのにな...

• 結論としては、DFS木に含まれる辺(span-edge)については「潜る」方向に、そうで無い辺(back-edge)については「遡る」方向に向きづければ良い。

#include<bits/stdc++.h>
using namespace std;

#define LIM 110

int N,M;
pair<int,int> edge[LIM * LIM * 2];
int g[LIM][LIM];
int c[LIM];

int visited[LIM],depth[LIM];
vector<int> graph[LIM];

bool dfstree[LIM][LIM];

void dfs(int x,int pre,int dpt){
    visited[x] = 1;
    depth[x] = dpt;
    for(auto e : graph[x]){
        if(e != pre && !visited[e]){
            dfstree[x][e] = dfstree[e][x] = true;
            dfs(e,x,dpt+1);
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> N >> M;
    for(int i = 0;i < M;i++){
        int a,b;cin >> a >> b;
        a--,b--;
        edge[i] = make_pair(a,b);
        g[a][b] = g[b][a] = 1;
    }
    for(int i = 0;i < N;i++){
        cin >> c[i];
    }
    
    // c[i] == c[j]の辺を無向辺で結ぶ
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            if(g[i][j] && (c[i] == c[j])){
                graph[i].push_back(j);
            }
        }
    }
    
    for(int i = 0;i < N;i++){
        if(!visited[i]){
            dfs(i,-1,0);
        }
    }
    
    for(int i = 0;i < M;i++){
        auto[a,b] = edge[i];
        if(c[a] > c[b]){
            cout << "->" << '\n';
        }else if(c[a] == c[b]){
            if(dfstree[a][b]){
                cout << (depth[a] < depth[b] ? "->" : "<-") << '\n';
            }else{
                cout << (depth[a] > depth[b] ? "->" : "<-") << '\n';
            }
        }else{
            cout << "<-" << '\n';
        }
    }
    
}