• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Gym101142C:CodeCodervsTopForces(强连通算法)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题意: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\n",sz[scc[i]]-1);
    return 0;
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap