Wall
National Olympiad · Municipal round
Submission name: stena.cpp
Problem summary
A rectangular wall consists of unit-height stones with integer lengths. Stones are numbered left to right, row by row from the top. All K supporting relationships are given: a b means stone a lies directly above stone b with positive-length contact. Determine the wall’s height.
Input
N K, then K pairs a b. The pairs are sorted by a, then b.
Output
One integer: the height in unit rows.
Constraints
2 ≤ N ≤ 100,000; 0 ≤ K ≤ 200,000; the relationships describe the stated wall.
Worked example
An independently prepared example for this explanation.
Input
4 3 1 2 2 3 3 4
Output
4
Solution analysis
- Direct every relationship from the upper stone to the lower stone. This graph is acyclic because edges go downward.
- Process vertices in topological order using indegrees and a queue.
- Set every initial path length to 1: even an isolated stone occupies one row.
- For each edge v→u, update length[u]=max(length[u],length[v]+1). The longest downward chain gives the height.
Why it works
Topological order places every possible predecessor before its destination, so the recurrence computes the longest chain ending at each stone. Any nonbottom stone has a supporting stone below it; a chain from the top through successive supports spans every row, and no chain can exceed the wall height.
Watch out. Count vertices in the chain, not edges. A single-row wall has height 1 even when K=0.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Topological order places every possible predecessor before its destination, so the
// recurrence computes the longest chain ending at each stone. Any nonbottom stone has a supporting
// stone below it; a chain from the top through successive supports spans every row, and no chain can
// exceed the wall height.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin>>n>>k;
vector<vector<int>>g(n+1);
vector<int>indegree(n+1),length(n+1,1);
for(int i=0;i<k;++i){
int a,b;
cin>>a>>b;
g[a].push_back(b);
++indegree[b];
}
queue<int>q;
for(int v=1;v<=n;++v){
if(!indegree[v]){
q.push(v);
}
}
int answer=1;
while(!q.empty()){
int v=q.front();
q.pop();
answer=max(answer,length[v]);
for(int u:g[v]){
length[u]=max(length[u],length[v]+1);
if(--indegree[u]==0){
q.push(u);
}
}
}
cout<<answer<<'\n';
}