鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

POJ 1904 强联通分量

来源:互联网 作者:佚名 时间:2016-05-12 15:56
点击打开链接 题意:不说题意了,直接说它让干什么把,我们要找每个王子可以娶的女人,并且他娶了其中一个剩下的王子依然可以找到老婆,也就是固定一条边后,剩下的关系还是可以构成一个完备二分图,然后每个王子能娶的公主从小到大输出 思路:这种题没做过

点击打开链接

题意:不说题意了,直接说它让干什么把,我们要找每个王子可以娶的女人,并且他娶了其中一个剩下的王子依然可以找到老婆,也就是固定一条边后,剩下的关系还是可以构成一个完备二分图,然后每个王子能娶的公主从小到大输出

思路:这种题没做过,看了看网上的题解,是要找强联通分量,那么可以肯定的是如果id号王子在强联通分量里,那么这里面的所有公主都满足条件,因为图是王子连公主,公主连王子的,我既然在一个联通分量里说明相互可达,那么也就是我这个王子可以到达所有的在这个联通分量的公主,而最后给的可以成功的分配方案是告诉你这样分配可以的嘛,那么将公主连向王子,跑强联通分量,分量里的王子可以到达所有这个分量里的公主,保存输出即可

#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=4010;
vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> vs;
bool used[maxn];
int cmp[maxn],V;
void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(int v){
    used[v]=1;
    for(int i=0;i<G[v].size();i++){
        if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
}
void rdfs(int v,int k){
    used[v]=1;
    cmp[v]=k;
    for(int i=0;i<rG[v].size();i++){
        if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
}
int scc(){
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0;v<V;v++) if(!used[v]) dfs(v);
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
        if(!used[vs[i]]) rdfs(vs[i],k++);
    }
    return k;
}
int num[maxn];
int main(){
    int a,b,c,n;
    while(scanf("%d",&n)!=-1){
        for(int i=0;i<maxn;i++){
            G[i].clear();
            rG[i].clear();
        }
        vs.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&a);
            while(a--){
                scanf("%d",&b);
                add_edge(i,b+n);
            }
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&a);
            add_edge(a+n,i);
        }
        V=2*n;
        int ans=scc();
        for(int i=1;i<=n;i++){
            int sum=0;
            for(int j=0;j<G[i].size();j++){
                int t=G[i][j];
                if(cmp[i]==cmp[t]){
                    num[sum++]=t;
                }
            }
            sort(num,num+sum);
            if(sum==0) printf("%d\n",sum);
            else printf("%d ",sum);
            for(int i=0;i<sum;i++){
                if(i==sum-1) printf("%d\n",num[i]-n);
                else printf("%d ",num[i]-n);
            }
        }
    }
    return 0;
}


网友评论
<