📝 문제 정보#
- 링크:
- 번역
문제#
Farmer John은 소들의 방목 패턴을 더 잘 관리하기 위해 농장 전체에 일방통행 소 길들을 설치했습니다. 농장은 N개의 목초지로 구성되어 있으며, 편의상 1부터 N까지 번호가 매겨져 있고, 각 일방통행 소 길은 한 쌍의 목초지를 연결합니다. 예를 들어, 목초지 X에서 목초지 Y로 연결되는 길이 있다면, 소들은 X에서 Y로는 이동할 수 있지만 Y에서 X로는 이동할 수 없습니다.
우리 모두가 알다시피, 소 Bessie는 가능한 한 많은 목초지에서 풀을 먹는 것을 좋아합니다. 그녀는 항상 하루의 시작에 목초지 1에서 출발하여 일련의 목초지들을 방문한 후, 하루가 끝날 때 목초지 1로 돌아옵니다. 그녀는 경로를 따라 방문하는 서로 다른 목초지의 수를 최대화하려고 합니다. 각 목초지에서 풀을 먹을 수 있기 때문입니다(한 목초지를 여러 번 방문하더라도, 그곳의 풀은 한 번만 먹습니다).
상상할 수 있듯이, Bessie는 FJ의 길에 대한 일방통행 제한에 대해 특별히 만족하지 않습니다. 이는 그녀가 일일 경로에서 방문할 수 있는 서로 다른 목초지의 수를 줄일 가능성이 높기 때문입니다. 그녀는 규칙을 어기고 최대 한 개의 길을 반대 방향으로 따라가면 얼마나 많은 풀을 먹을 수 있을지 궁금합니다. 목초지 1에서 시작하여 목초지 1로 끝나는 경로를 따라 최대 한 개의 길을 반대 방향으로 따라갈 수 있을 때, 그녀가 방문할 수 있는 서로 다른 목초지의 최대 개수를 계산하세요. Bessie는 여정 중 최대 한 번만 뒤로 이동할 수 있습니다. 특히, 같은 길을 두 번 역방향으로 갈 수는 없습니다.
입력#
첫 번째 줄에는 N과 M이 주어지며, 목초지의 개수와 일방통행 길의 개수를 나타냅니다 (1 ≤ N, M ≤ 100,000).
다음 M개의 줄에는 각각 일방통행 소 길이 설명됩니다. 각 줄에는 두 개의 서로 다른 목초지 번호 X와 Y가 포함되며, X에서 Y로 가는 소 길에 해당합니다. 같은 소 길이 두 번 이상 나타나지 않습니다.
출력#
목초지 1에서 시작하여 목초지 1로 끝나는 경로를 따라 Bessie가 방문할 수 있는 서로 다른 목초지의 최대 개수를 나타내는 한 줄을 출력합니다. 단, 경로를 따라 최대 한 개의 길을 반대 방향으로 따라갈 수 있습니다.
🧐 관찰 및 접근#
- 어떤 간선 하나를 뒤집은 간선 하나를 추가해서, 정점 1로 돌아올 수 있으면서 가장 많은 정점 들리기..
- 어떤 간선이 한 SCC 안에 속한다면, 해당 간선은 뒤집을 필요가 없다.
- 우회경로가 있으니까 큰 의미가 없다.
- 그럼 이제 SCC끼리 묶어서 DAG로 생각하자.
- ![[Drawing 2026-01-28 10.34.24.excalidraw.png]]
- 예제 입력 1번의 그림은 다음과 같다. 빨간색 간선을 뒤집었고, 1 -> (2, 4, 7) -> 5 -> 3 -> 1로 돌아온다.
- 직관적으로 생각나는 풀이들은 이렇다.
- 풀이 1
- 어떤 간선 하나를 무시한다. (뒤집을 간선)
- 이때 해당 간선의 시점에서 시작해서 종점까지 오는 DAG DP를 진행해서 최댓값을 구한다. 정점 1을 지나야함에 유의한다.
- 아까 제외한 간선을 뒤집으면 회로를 만들 수 있다.
- 풀이 2
- 정점 1에서 DAG DP를 돌린다.
- 각 정점에서 간선을 한번만 뒤집어서 정점 1로 들어올 수 있는지 체크한다.
- 풀이 1
- 풀이 2에 가까운 맛일 것 같은데, 정점을 중복으로 세진 않을까? 라는 의문이 먼저 든다.
- 그런데, 그런 상황이면 SCC로 묶였을수도 있지 않을까?
- $1 \to x_1 \to x_2 \to \cdots \to x_n$ 으로 가는 경로가 있었다고 생각해보자.
- ![[Drawing 2026-01-28 10.42.46.excalidraw.png]]
- 이때, 우리는 $x_1$로 돌아가는게 목표이므로, 어떤 간선 $x_k \to x_n$을 뒤집기로 마음먹었다면 $x_k$에서 $x_1$로 가는 경로가 있어야한다.
- 이 때, 뒤집지 않은 그래프에서 $x_1 \to x_k$가 가능했으므로, 그러한 간선이 있었다면 $x_1 \to x_k$는 사이클이다!!!
- 따라서, 간선을 한번만 뒤집었을때 정점 1로 돌아올 수 있다면 그 경로에서 해당 정점은 세진적이 없다.
- 간선 1로 들어갈 수 있는 모든 정점들을 찾자. 이때의 최댓값은 기존의 DAG에서 모든 간선을 뒤집는 것으로 만들 수 있는 것 같다.
- 이후, 기존 그래프의 간선 $(u, v) \in E$ 에 대해 $\text{DP}[v] + \text{DP2}[u]$ 의 최댓값이 답이다. 첫 사이클에서만 도는 경우는 잘 처리하면 되겠지
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
DirectedGraph graph(N);
rep(i, 0, M){
int u, v; cin >> u >> v;
u--; v--;
graph.add_edge(u, v);
}
DirectedGraph dag = graph.getCompressedGraph();
// calc DP1 = start from node 1, max sum of vertex count
int sz = dag.V;
vector<int> indeg(sz, 0), val(sz, 0);
rep(i, 0, N) val[graph.sccId[i]]++;
rep(cur, 0, sz) for(auto &nxt: dag.links[cur]) indeg[nxt]++;
vector<int> DP1(sz, -1e9), DP2(sz, -1e9);
int start = graph.sccId[0];
DP1[start] = val[start];
queue<int> Q;
rep(i, 0, sz) if(indeg[i] == 0) Q.push(i);
while(!Q.empty()){
int cur = Q.front(); Q.pop();
for(auto &nxt: dag.links[cur]){
DP1[nxt] = max(DP1[nxt], DP1[cur] + val[nxt]);
indeg[nxt]--;
if(indeg[nxt] == 0) Q.push(nxt);
}
}
// calc DP2 = on fliped graph, to node 1, max sum of vertex count
DirectedGraph rev_dag(sz);
rep(cur, 0, sz) for(auto &nxt: dag.links[cur]) rev_dag.add_edge(nxt, cur);
rep(i, 0, sz) indeg[i] = 0;
rep(cur, 0, sz) for(auto &nxt: rev_dag.links[cur]) indeg[nxt]++;
rep(i, 0, sz) if(indeg[i] == 0) Q.push(i);
DP2[start] = val[start];
while(!Q.empty()){
int cur = Q.front(); Q.pop();
for(auto &nxt: rev_dag.links[cur]){
DP2[nxt] = max(DP2[nxt], DP2[cur] + val[nxt]);
indeg[nxt]--;
if(indeg[nxt] == 0) Q.push(nxt);
}
}
int ans = val[start];
rep(u, 0, N) for(auto &nxt: graph.links[u]){
int su = graph.sccId[u];
int sv = graph.sccId[nxt];
if(su == sv) continue;
ans = max(ans, DP1[sv] + DP2[su] - val[start]);
}
cout << ans << "\n";
}