Gym 101142C ：CodeCoder vs TopForces（强连通算法）

题意：N个人，每个人有a属性和b属性，如果一个人的a或者b大于另外一个人，我们说这个人可以打败那个人。且这种关系可以传递。对于每个人，输出他可以打败多少人。（保证每个a不相同，保证每个b不相同。

思路：对于a关系，我们按重小到大连边，b同理。然后每个点能到的点就是可以打败的点。即是缩点后乱搞。

（此题是图，而不是排序后的数据结构题。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=1000100;
vector<int>G1[maxn],G2[maxn];
pii p1[maxn],p2[maxn];
int dfn[maxn],low[maxn],scc[maxn],scc_cnt,sz[maxn],ind[maxn];
int q[maxn],head,tail,times,ans[maxn],res[maxn],instk[maxn];
map<pii,int>mp;
void tarjan(int u)
{
    instk[u]=1; q[++head]=u;
    dfn[u]=low[u]=++times;
    for(int i=0;i<G1[u].size();i++){
        int v=G1[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instk[v])low[u]=min(low[u],dfn[v]);//无向图与有向图的区别
    }
    if(dfn[u]==low[u]){
        scc_cnt++;
        while(true){
             int x=q[head--];
             scc[x]=scc_cnt; sz[scc_cnt]++;
             instk[x]=0;
             if(x==u) break;
        }     
    }
}
int main()
{
    int N,i,j;
    scanf("%d",&N);
    for(i=1;i<=N;i++) scanf("%d%d",&p1[i].F,&p2[i].F),p1[i].S=p2[i].S=i;
    sort(p1+1,p1+N+1);
    sort(p2+1,p2+N+1);
    for(i=2;i<=N;i++) G1[p1[i].S].push_back(p1[i-1].S);
    for(i=2;i<=N;i++) G1[p2[i].S].push_back(p2[i-1].S);
    for(i=1;i<=N;i++) if(!dfn[i]) tarjan(i);
    for(i=1;i<=N;i++){
        int L=G1[i].size();
        for(j=0;j<L;j++){
            if(scc[i]!=scc[G1[i][j]]&&!mp[make_pair(scc[G1[i][j]],scc[i])]) mp[make_pair(scc[G1[i][j]],scc[i])]=1,G2[scc[G1[i][j]]].push_back(scc[i]),ind[scc[i]]++;
        }
    }
    head=tail=0;
    for(i=1;i<=scc_cnt;i++) if(ind[i]==0) q[++head]=i;
    while(tail<head){
        int u=q[++tail];
        int L=G2[u].size();
        for(j=0;j<L;j++){
            sz[G2[u][j]]+=sz[u];
            if((--ind[G2[u][j]])==0) q[++head]=G2[u][j];
        }
    }
    for(i=1;i<=N;i++) printf("%d
",sz[scc[i]]-1);
    return 0;
}