写在前面

建议加强数据；本题我用了两种写法

$Idea$

这道题是$LIS$。怎么想呢？

我们把北岸排好序之后会有$a[i_1].n<a[i_2].n,(i_1<i_2)$；假如对于$i_1,i_2$,它们的南岸坐标$a[i_1].s<a[i_2].s$，那么就会有交叉，而所有城市的友好城市不相同，所以我们应该建造一个严格上升的子序列。

那么求得就是$LIS$。

多种方法：1. $DP$，2.树状数组,3.线段树.等等

$Code$

$Code1$

//DP
const int maxn=200005; 
int Stack[maxn];
struct node{
    int a,b;
    inline bool operator<(const node&x)const{return a<x.a;}
}f[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>f[i].a>>f[i].b;
    sort(f,f+n);
    int ans=0;
    for(int i=0;i<n;i++){
        if(f[i].b>Stack[ans])
            Stack[++ans]=f[i].b;
        else{
            int l=1,r=ans;
            while(l<r){
                int mid=l+r>>1;
                if(f[i].b>Stack[mid])
                    l=mid+1;
                else
                    r=mid;
            }
            Stack[l]=f[i].b;
        }
    }
    cout<<ans;
    return 0;
}

$Code2$

//树状数组
const int MAXX=1e6;
int n,maxx;
struct node{
    int n,s;
    inline bool operator<(const node&x)const{return n<x.n;}
}l[maxn];
int tree[MAXX],ans;        
inline void add(int x,int v){
    while(x<=maxx){   //因为下标是横坐标，所以最大为maxx
        tree[x]=max(tree[x],v);
        x+=x&(-x);
    }
}
inline int ask(int x){
    int ret=0;
    while(x){
        ret=max(ret,tree[x]);
        x-=x&(-x);
    }
    return ret;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        l[i].s=read(); l[i].n=read();
        maxx=max(maxx,l[i].s);
    }
    sort(l+1,l+n+1);  //别忘了排序，之后就和北岸坐标没关系了。
    for(int i=1;i<=n;i++){
        int x=ask(l[i].s)+1;
        ans=max(ans,x);
        add(l[i].s+1,x);
    }
    printf("%d",ans);
    return 0;
}

博客推销:
1. $cnblogs$
2. $Luogu\;blog$

$$ The \quad End $$

$$ 是我入戏太深，结局却一个人；原地傻傻的等，换不回那温存。-《入戏太深》马旭东 $$