题解

44 条题解

  • 7
    @ 2017-09-21 21:42:06

    用的tarjan算法,1A,总耗时25MS,难度还可以。题目分析如下:
    1.本题的爱心天使其实就是那些**元素个数大于1**的强连通分量。
    2.某个爱心天使被其他所有人或爱心天使所爱,就是那个**出度为0 元素个数大于1**的强连通分量,**同样要保证这样的爱心天使有且只有一个。否则输出-1**.
    3.**注意**最后输出时的顺序是**从小到大**的!!!
    如果实在A不了,可以先去试试**VIJOS-P1023 Victoria的舞会3**,算法可以使一样的。
    附上C++代码:

    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    int low[1001];//low[x]为x或x的子树能够追溯到的最早的栈中节点的次序号。
    int deep[1001];//定义deep[x]为节点x搜索的次序编号(时间戳,即搜索x的深度)。
    int zhan[1001];//栈数组。
    int ans[1001][1001];//ans[k][0]存储的是ans[k][i]中的i的个数,即子图中节点个数。
    int belong[1001];//缩点用数组,记录每个节点x的所在强连通分量的编号。
    int newrd[1001];//缩点后点的入度。
    int newcd[1001];//缩点后点的出度。
    bool ts[1001];//判断是否天使即素个数大于1的强连通分量。
    bool inzhan[1001];//是否在栈中。
    bool vis[1001];//是否被搜过。
    bool a[1001][1001];//从i到j如果有单向边i=>j则a[i][j]=1。
    int tot=0;
    int top=1;//栈中该放的位置。
    int ans1=0;
    int cnt=0;
    int min(int a,int b)
    {
        if(a<b)
            return a;
        return b;
    }
    void tarjan(int p,int n)
    {
        zhan[++top]=p;
        vis[p]=1;
        inzhan[p]=1;
        tot++;
        deep[p]=tot;
        low[p]=tot;
        for(int i=1;i<=n;i++)
            if(a[p][i]==1)
            {
                if(vis[i]==0)
                {
                    tarjan(i,n);
                    low[p]=min(low[p],low[i]);
                }
                else
                if(inzhan[i]==1)
                    low[p]=min(low[p],deep[i]);
            }
        if(deep[p]==low[p])
        {
            ans1++;
            int top1;
            do
            {
                top1=zhan[top--];
                inzhan[top1]=0;
                ans[ans1][++ans[ans1][0]]=top1;
            }
            while(top1!=p);
        }
    }
    int main()
    {
        int n, m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x, y;
            scanf("%d%d",&x,&y);
            a[x][y]=1;//记录边。
        }
        for(int i=1;i<=n;i++)
            if(deep[i]==0)
                tarjan(i,n);//因为此题中没有介绍是否联通,所以用了这种方式tarjan。
                //在每次tarjan(i,n)后,和i联通的点都被处理过,即deep[处理过的点]!=0;
        for(int i=1;i<=ans1;i++)
            for(int j=1;j<=ans[i][0];j++)
                belong[ans[i][j]]=i;//记录每个节点x的所在强连通分量的编号。
        for(int i=1;i<=ans1;i++)
            if(ans[i][0]>1)
            {
                cnt++;
                ts[i]=1;//记录天使个数,将天使(强连通分量)的标号存起来。
            }
        printf("%d\n",cnt);//第一问bingo,天使个数。
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]==1&&belong[i]!=belong[j])
                {
                    newcd[belong[i]]++;
                    newrd[belong[j]]++;//更新缩点后点的入度,出度。
                }
            }
        int idx;
        int idx2=0;
        for(int i=1;i<=n;i++)
            if(newcd[i]==0&&ts[i]==1)
            {
                idx=i;
                idx2++;//判断是否唯一。
            } 
        if(idx2!=1)
            printf("-1");
        if(idx2==1)
        {
            sort(ans[idx]+1,ans[idx]+1+ans[idx][0]);
            for(int i=1;i<=ans[idx][0];i++)
            {
                if(i==ans[idx][0])
                {
                    printf("%d",ans[idx][i]);
                    return 0;
                }
                printf("%d ",ans[idx][i]); //处理格式,不知有没有必要。
            }
        }
    }//第一次发题解xixi。。
     //如有说的不对,或者不懂的地方,欢迎提出,指正。
    
    • @ 2018-09-03 11:06:57

      好评
      emmmm...

  • 5
    @ 2017-09-09 17:58:21

    上一次做这道题是在5月前,今天又考了tarjan,终于才ac了。
    说实话,这道题略微有点坑。

    注意!题中的 “爱心天使” 即是 “大小至少为2(即包含两个点)的强联通分量” 。
    至于怎么证明,想想当强联通分量出现的时候,“爱” 的传递性是不是刚好能使整个分量的内部的每个点互相通达,此时的 “该分量强联通” 正是成为 “爱心天使” 最基本条件。

    这道题问题初读很容易读错,所以想做这道题,那就先要搞清楚问题是什么:

    1. 第一问:图的强联通分量的数量。
    2. 第二问:图中是否存在一个强联通分量,使其他所有点都能到达这个强联通分量。

    特别是第二问,处理起来有点麻烦。

    然而数据中还有很多图的特殊情况,此处列举下,方便大家分析:

    1. 图可能不连通,含有不连通的强联通分量。
    2. 整个图可能即为唯一的强联通分量(这叫强联通图?是吗?)。
    3. 图中根本就没有强联通分量。

    我的解法到很简单:

    一遍tarjan求出强联通分量;扫一遍统计“爱心天使”,随带求出每个强联通分量(包含大小为1的强联通分量)的出度(类似缩点),最后又一遍统计出度为0的“爱心天使”数量,看是否存在唯一情况,最后输出答案。

    代码不太容易看,我的变量的命名太丑了:

    #include <stack>
    #include <vector>
    #include <iostream>
    using namespace std;
    int N, M;
    int G, H;
    stack<int> S;
    vector<int> E[1005];
    int I[1005], O[1005], V[1005], C[1005], D[1005], L[1005], Z[1005];
    void TARJAN (int x) {
        
        V[x]=1;
        S.push(x);
        L[x]=D[x]=++G;
        int v;
        for(int i=0; i<E[x].size(); i++) {
            v=E[x][i];  
            if (!D[v]) {
                TARJAN(v);  
                L[x]=min(L[x], L[v]);
            }
            else if (V[v]) L[x]=min(L[x], D[v]);
        }
        if (L[x]==D[x]) {
            V[x]=0;
            C[x]=++H;
            Z[H]++;
            while(S.top()!=x) {
                V[S.top()]=0;
                C[S.top()]=H;
                Z[H]++;
                S.pop();
            }
            S.pop();
        }
        
    }
    int main () {
        
        cin >> N >> M;
        int u, v;
        for(int i=1; i<=M; i++) {
            cin >> u >> v;
            E[u].push_back(v);  
            I[v]++;
        }
        for(int i=1; i<=N ; i++) 
            if (!D[i]) TARJAN(i);
        int a=0, b=0;
        for(int i=1; i<=H; i++) 
            if (Z[i]>1) a++;
        cout << a << endl;  
        for(int i=1; i<=N; i++) 
            for(int j=0; j<E[i].size(); j++) {
                v=E[i][j];
                if (C[i]!=C[v]) O[C[i]]++;  
            }
        for(int i=1; i<=H; i++) 
            if (Z[i]>1&&(!O[i])) b++;    
        if (b==1) {
            for(int i=1; i<=N; i++)
                if (!O[C[i]]) cout << i << " "; 
        }
        else cout << "-1";
        return 0;
        
    }
    
  • 2
    @ 2018-10-30 08:11:52
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #define For(i,l,r) for(int i=l;i<=r;i++)
    #define Dor(i,l,r) for(int i=l;i>=r;i--)
    #define N 1005
    using namespace std;
    
    //核心:tarjan求强连通分量 
    int n,m,sig,color[N],visit[N],dfn[N],low[N],cnt,tt,degree[N],num[N],judge,ans1,ans2;
    int stack[N];
    vector <int> to[N];
    void tarjan(int v){
        visit[v]=1;
        dfn[v]=low[v]=++cnt;
        stack[++tt]=v;
        for(int i=0;i<to[v].size();i++){
            int u=to[v][i];
            if (visit[u]==0) tarjan(u);
            if (visit[u]==1) low[v]=min(low[v],low[u]); 
        }
        if (low[v]==dfn[v]){
            sig++;
            do{
                color[stack[tt]]=sig;
                visit[stack[tt]]=-1;
            }
            while (stack[tt--]!=v);
        }//利用栈进行染色 
    }
    void work(){
        tt=-1;
        For(i,1,n){
            if (!visit[i]) tarjan(i);
        }
        For(i,1,n){
            for(int j=0;j<to[i].size();j++){
                int v=to[i][j];
                if (color[i]!=color[v]){
                    degree[color[i]]++;//记录出度 
                } 
            } 
        }
        For(i,1,sig){
            if (degree[i]==0) judge++,ans2=i;//出度为0则记录 
            For(j,1,n){
                if (color[j]==i) num[i]++;
            }
            if (num[i]>=2) ans1++;//只有当强连通分量结点数>2记录 
        }
        printf("%d\n",ans1);
        if (judge>1 || num[ans2]<2) printf("-1\n");//方案不唯一或者不满足条件 
            else{
                For(i,1,n){
                    if (color[i]==ans2) printf("%d ",i);
                }
            }
            
    } 
    int main(){
        scanf("%d%d",&n,&m);
        For(i,1,m){
            int x,y;
            scanf("%d%d",&x,&y);
            to[x].push_back(y);  
        }
        work();
        return 0;
    } 
    
  • 1
    @ 2018-09-05 12:29:54

    这题意很不明。。。数据太水
    下面这个数据可以Hack掉大部分已经AC的代码,题解区里的AC代码跑出来的结果都不一样
    5 5
    1 2
    2 1
    3 4
    4 3
    2 5

  • 1
    @ 2009-08-23 08:24:43

    求强连通。

    然后分开。

    把强连通收缩成一个点。

    接下来floyed一遍,找出一个点,每个点都可已到达

  • 1
    @ 2009-08-23 07:40:29

    后两个数据过不了啊

    总超时

  • 1
    @ 2009-08-22 11:56:59

    恩。。不错

  • 1
    @ 2009-08-25 08:54:53

    不用缩点直接过

    就是最后2个点400多MS

    偶菜不知道标称给个那个什么算法 用的N^3居然也过了,可见数据之若啊

    直接在

    for k:=1 to n do

    for i:=1 to n do

    if flag then

    for j:=1 to n do

    flag:=flag or (flagand flag[k,j]);

    即可AC

  • 0
    @ 2019-11-12 14:30:34

    跟受欢迎的牛类似

    #include<cstdio>
    #include<stack>
    #include<cstring>
    
    inline int min(int x,int y){return x<y?x:y;}
    
    int n,m,cnt,dfn[10005],low[10005],color[10005],vis[10005],ans,
        outd[10005],head[10005],num[10005],tarclock,colorclock,tot,qvq;
    
    struct edge{
        int v,next;
    }e[50005];
    
    inline void add(int u,int v){
        e[++cnt].v=v;
        e[cnt].next=head[u];
        head[u]=cnt;
    }
    
    std::stack<int> s;
    
    inline void tarjan(int u){
        dfn[u]=low[u]=++tarclock;
        vis[u]=1;
        s.push(u);
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(vis[v])low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
            colorclock++;
            while(1){
                int x=s.top();
                s.pop();
                color[x]=colorclock;
                vis[x]=0;
                num[colorclock]++;
                if(x==u)break;
            }
        }
    }
        
    int main(){
        //freopen("love.in","r",stdin);
        //freopen("love.out","w",stdout);   
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i])tarjan(i);
        }
        for(int u=1;u<=n;u++){
            for(int i=head[u];i!=-1;i=e[i].next){
                int v=e[i].v;
                if(color[u]!=color[v]){
                    outd[color[u]]++;
                }
            }
        }
        for(int i=1;i<=colorclock;i++){
            if(num[i]!=1)ans++;
            if(!outd[i]){tot++;qvq=i;}//即使不是爱心天使也要统计
        }
        printf("%d\n",ans);
        if(tot==1&&num[qvq]>1){
            for(int i=1;i<=n;i++)
                if(color[i]==qvq)printf("%d ",i);
        }
        else printf("-1\n");
    }
    
  • 0
    @ 2019-05-18 22:03:35

    同思路,tarjan+乱搞

    第一问:求元素个数大于1的连通分量
    第二问:求出度为0,且元素个数大于1的连通分量中的所有元素
    哪位大佬告诉我为啥是统计出度为0?而不是统计入度>0?

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    typedef struct EDGE
    {
        int node;
        struct EDGE *next=NULL;
    }edge;
    
    int n,m;
    int dfn[1001]={0};
    int low[1001]={0};
    bool vis[1001]={0};
    edge *node[1001]={0};
    int color[1001]={0};
    int nowd=0;
    int cacc=0;
    int cd[1001]={0};
    vector<int> vint;
    int um[1001]={0};
    int ans=0;
    
    void tarjan(int x)
    {
        nowd++;
        dfn[x]=nowd;
        low[x]=nowd;
        vis[x]=true;
        vint.push_back(x);
        edge *p=node[x];
        while(p!=NULL)
        {
            if(!dfn[p->node])
            {
                tarjan(p->node);
                low[x]=min(low[x],low[p->node]);
            }
            else if(vis[p->node])
            {
                low[x]=min(low[x],dfn[p->node]);
            }
            p=p->next;
        }
        int a;
        if(dfn[x]==low[x])
        {
            cacc++;
            color[x]=cacc;
            vis[x]=false;
            while(vint[vint.size()-1]!=x)
            {
                a=vint[vint.size()-1];
                color[a]=cacc;
                vis[a]=false;
                vint.pop_back();
            }
            vint.pop_back();
        }
    }
    
    int main()
    {
        cin>>n>>m;
        int i,j,k;
        edge *p,*last;
        for(i=0;i<m;i++)
        {
            cin>>j>>k;
            if(node[j]==NULL)
            {
                node[j]=new edge;
                node[j]->node=k;
            }
            else
            {
                p=node[j];
                while(p!=NULL)
                {
                    last=p;
                    p=p->next;
                }
                p=new edge;
                p->node=k;
                last->next=p;
            }
        }
        for(i=1;i<=n;i++)
        {
            if(!dfn[i])
            {
                tarjan(i);
            }
        }
        for(i=1;i<=n;i++)
        {
            um[color[i]]++;
            p=node[i];
            while(p!=NULL)
            {
                if(color[i]!=color[p->node])
                {
                    cd[color[i]]++;
                }
                p=p->next;
            }
        }
        for(i=1;i<=cacc;i++)
        {
            if(um[i]>1)
            {
                ans++;
            }
        }
        cout<<ans<<endl;
        bool check=true;
        vint.clear();
        for(i=1;i<=cacc;i++)
        {
            if(cd[i]==0&&um[i]>1)
            {
                vint.push_back(i);
            }
        }
        if(vint.size()!=1)
        {
            cout<<-1<<endl;
        }
        else
        {
            k=vint[0];
            for(i=1;i<=n;i++)
            {
                if(color[i]==k)
                {
                    if(check)
                    {
                        cout<<i;
                        check=false;
                    }
                    else
                    {
                        cout<<' '<<i;
                    }
                }
            }
            cout<<endl;
        }
        return 0;
    }
    
  • 0
    @ 2017-11-11 20:07:02

    我的题解有两步:
    1、targan求强联通分量个数,同时将在同一个强联通分量的点染色
    2、统计每个强联通分量的出度
    题目第一问的意思是:问图中有几个强联通分量
    题目第二问的意思是:如果有一个强联通分量的出度为0(即别的人都爱他),则从小到大输出这个强联通分量内的天使,如果有多个则输出-1
    #include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    vector<int> e[10001];//存储边
    stack<int> q;
    int dra[1001],out[1001];//dra为给每个强联通分量染色,out为计算每个强联通分量的出度
    int dfn[1001],low[1001];//targan两个重要的数组
    int cnt,tot,color;//cnt为遍历的步数,color为染色数
    int ans[10001];//统计每个强联通分量的点数
    bool vis[1001];//标记这个点是否在栈中
    void targan(int u)
    {
    q.push(u);
    vis[u]=1;
    low[u]=dfn[u]=++cnt;
    for(int i=0;i<e[u].size();++i)
    {
    int v=e[u][i];
    if(!dfn[v])
    {
    targan(v);//深搜遍历
    low[u]=min(low[u],low[v]);//更新树枝边
    }
    else if(vis[v])
    {
    low[u]=min(low[u],dfn[v]);//在找到最早被targan过的根节点时更新反向边,从而更新树枝边
    }
    }
    if(low[u]==dfn[u])//已经找到了一个强联通分量
    {
    int v;
    ++cnt;
    while(v!=u)
    {
    v=q.top();
    q.pop() ;
    vis[v]=0;//出栈就要取消标记,某个点如果已经被targan遍历过(即dfn[i]!=0),同时还不在栈中,那么一定就是另外一个强联通分量
    ans[cnt]++;//统计每个强联通分量的点数
    dra[v]=cnt;//染色
    }
    }
    }
    int main()
    {
    int n,m,u,v,a=0,b=0;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
    cin>>u>>v;
    e[u].push_back(v);
    }
    for(int i=1;i<=n;++i)
    if(!dfn[i])targan(i);
    for(int i=1;i<=cnt;++i)
    if(ans[i]>1)++a;
    cout<<a<<endl;//输出强联通分量个数
    for(int i=1;i<=n;++i)
    for(int j=0;j<e[i].size();++j)
    {
    v=e[i][j];
    if(dra[i]!=dra[v])out[dra[i]]++;//统计不同的强联通分量的出度
    }
    for(int i=1;i<=cnt;++i)
    {
    if(ans[i]>1&&out[i]==0)
    ++b;//统计有几个出度为1的强联通分量
    }
    if(b==1)
    {
    for(int i=1;i<=n;++i)
    if(out[dra[i]]==0)cout<<i<<" "; //从小到大输出
    }
    else cout<<"-1"<<endl;
    return 0;
    }

  • 0
    @ 2016-10-17 23:50:31

    第一次写tarjan就一遍AC。。。RP+++
    注意第一问的强连通分量里至少要有2个人
    第二问的话,DFS暴力可好...

  • 0
    @ 2016-06-06 23:34:01

    第一问直接用tarjan算法
    也要保存一下,用一个点的编号标识这个强连通分量,在belong数组中
    把每个处于这个强连通分量中的点,都设成这个。
    第二问先缩点,当没有出度的那个强连通分量就是所求的对象
    若有多个这样的强连通分量,则说明此图不连通,即输出-1

    '/*
    *codevs.cn &Vijos.org
    *Problem#2822 & Problem#1626
    *Accepted & Accepted
    *Time:2ms & 0ms
    *Memory:256k & 584k
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<stack>
    #define _min(a,b) ((a)<(b))?(a):(b)
    using namespace std;
    typedef bool boolean;
    typedef class Edge{
    public:
    int end;
    int next;
    Edge():end(0),next(0){}
    Edge(int end,int next):end(end),next(next){}
    }Edge;
    Edge *edge;
    int n,m;
    int *head;
    int top;
    inline void addEdge(int from,int end){
    top++;
    edge[top].next=head[from];
    edge[top].end=end;
    head[from]=top;
    }
    //Tanjan�㷨,���
    boolean *visited;
    boolean *isCir;
    int *visitID;
    int *exitID;
    int entryed;
    stack<int> sta;
    int *belong;
    boolean *inStack;
    int _count;
    void getSonMap(int end){
    int now=-1;
    int exits=0;
    while(now!=end){
    now=sta.top();
    belong[now]=end;
    inStack[now]=false;
    exits++;
    sta.pop();
    }
    if(exits>1){
    _count++;
    isCir[now]=true;
    }
    }
    void Tarjan(const int pi){
    int index=head[pi];
    visitID[pi]=++entryed;
    exitID[pi]=visitID[pi];
    visited[pi]=true;
    inStack[pi]=true;
    sta.push(pi);
    while(index!=0){
    if(!visited[edge[index].end]){
    Tarjan(edge[index].end);
    exitID[pi]=_min(exitID[pi],exitID[edge[index].end]);
    }else if(inStack[edge[index].end]){
    exitID[pi]=_min(exitID[pi],visitID[edge[index].end]);
    }
    index=edge[index].next;
    }
    if(exitID[pi]==visitID[pi]){
    getSonMap(pi);
    }
    }
    int outgoing;
    void rebuild(){
    for(int i=1;i<=n;i++){
    for(int j=head[i];j!=0;j=edge[j].next){
    if(belong[edge[j].end]!=belong[i])
    outgoing[belong[i]]++;
    }
    }
    int result = 0;
    int id;
    for(int i=1;i<=n;i++){
    if(outgoing[i]==0&&isCir[i]){
    result++;
    id=belong[i];
    }
    }
    if(result==1){
    for(int i=1;i<=n;i++){
    if(belong[i]==id){
    printf("%d ",i);
    }
    }
    }else{
    printf("-1");
    }
    }
    int main(){
    cin>>n>>m;
    head=new int[(const int)(n+1)];
    edge=new Edge[(const int)(m+1)];
    visited=new boolean[(const int)(n+1)];
    visitID=new int[(const int)(n+1)];
    exitID=new int[(const int)(n+1)];
    belong=new int[(const int)(n+1)];
    inStack=new boolean[(const int)(n+1)];
    isCir=new boolean[(const int)(n+1)];
    memset(head,0,sizeof(int)
    (n+1));
    memset(visited,false,sizeof(boolean)*(n+1));
    memset(inStack,false,sizeof(boolean)*(n+1));
    memset(isCir,false,sizeof(boolean)*(n+1));
    for(int i=1;i<=m;i++){
    int f,e;
    scanf("%d%d",&f,&e);
    addEdge(f,e);
    }
    for(int i=1;i<=n;i++) belong[i]=i;
    for(int i=1;i<=n;i++){
    if(!visited[i])
    Tarjan(i);
    }
    cout<<_count<<endl;
    delete[] visited;
    delete[] inStack;
    // visited=new boolean[(const int)(n+1)];
    // inStack=new boolean[(const int)(n+1)];
    // memset(visited,false,sizeof(boolean)*(n+1));
    // memset(inStack,false,sizeof(boolean)*(n+1));
    outgoing=new int[(const int)(n+1)];
    memset(outgoing,0,sizeof(int)*(n+1));
    rebuild();
    return 0;
    }
    '

  • 0
    @ 2015-10-15 13:42:59

    type tlist=array[1..5000,1..5000] of longint;
    var i,j,k:longint;
    q:array[0..10000,1..3] of longint;
    qx:array[0..1000] of longint;
    d:array[0..1000] of longint;
    a:array[1..1000,1..2] of longint;
    b:array[1..1000] of boolean;
    c:tlist;
    t:array[1..5000] of longint;
    f:array[1..5000] of longint;
    n,m,ans,s,v,f1,f2,ts:int64;
    procedure dfs(x:int64);
    var i,now:longint;
    begin
    i:=qx[x];
    now:=d[0];
    while i<>0 do
    begin
    inc(d[0]);
    if b[q[i,2]] then
    begin
    if a[q[i,2],1]=0 then
    begin
    d[d[0]]:=q[i,2];
    a[d[d[0]],1]:=d[0];
    a[d[d[0]],2]:=d[0];
    dfs(q[i,2]);
    if d[0]>now then a[d[now],2]:=a[d[now+1],2];
    end
    else
    begin
    dec(d[0]);
    a[d[d[0]],2]:=a[q[i,2],1];
    end;
    end else dec(d[0]);
    i:=q[i,3];
    end;
    if a[d[now],1]=a[d[now],2] then
    begin
    inc(v);
    t[v]:=d[0]+1-now;
    inc(s,t[v]);
    for j:=now to d[0] do
    begin
    c[v,j-now+1]:=d[j];
    a[d[j],1]:=v;
    a[d[j],2]:=0;
    b[d[j]]:=false;
    d[j]:=0;
    end;
    dec(d[0],t[v]);
    if t[v]>1 then inc(ans);
    end;
    end;
    procedure duru; inline;
    begin
    read(n,m);
    fillchar(b,sizeof(b),true);
    for i:=1 to m do
    begin
    read(q[i,1],q[i,2]);
    q[i,3]:=qx[q[i,1]];
    qx[q[i,1]]:=i;
    end;
    end;
    function find(x:int64):int64;
    begin
    if f[x]=x then exit(x) else f[x]:=find(f[x]);
    exit(f[x]);
    end;
    procedure qsort(var a:tlist);
    procedure sort(l,r:longint);
    var i,j,x,y:longint;
    begin
    i:=l;
    j:=r;
    x:=a[k,(l+r) div 2];
    repeat
    while a[k,i]<x do inc(i);
    while x<a[k,j] do dec(j);
    if not(i>j) then
    begin
    y:=a[k,i];
    a[k,i]:=a[k,j];
    a[k,j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
    end;
    begin
    sort(1,ts);
    end;
    begin
    duru;
    while s<>n do
    begin
    for i:=1 to n do
    if b[i] then
    begin
    d[0]:=1;
    d[d[0]]:=i;
    a[d[1],1]:=1;
    a[d[1],2]:=1;
    break;
    end;
    dfs(i);
    end;
    writeln(ans);
    if ans>0 then
    begin
    for i:=1 to v do f[i]:=i;
    for i:=1 to m do
    begin
    f1:=find(a[q[i,1],1]);
    f2:=find(a[q[i,2],1]);
    if f1<>f2 then
    begin
    f[f1]:=f2;
    inc(t[f2],t[f1]);
    end;
    end;
    for k:=1 to v do
    if t[k]=n then
    begin
    for j:=1 to t[k] do
    if c[k,j]<>0 then inc(ts) else break;
    qsort(c);
    for j:=1 to ts-1 do
    write(c[k,j],' ');
    writeln(c[k,ts]);
    halt;
    end;
    end;
    writeln(-1);
    end.
    一遍Tarjan(找爱的天使个数)+并查集(找大家都爱的天使),就过了。
    测试数据 #0: Accepted, time = 3 ms, mem = 98784 KiB, score = 10
    测试数据 #1: Accepted, time = 5 ms, mem = 98788 KiB, score = 10
    测试数据 #2: Accepted, time = 4 ms, mem = 98784 KiB, score = 10
    测试数据 #3: Accepted, time = 5 ms, mem = 98784 KiB, score = 10
    测试数据 #4: Accepted, time = 4 ms, mem = 98784 KiB, score = 10
    测试数据 #5: Accepted, time = 3 ms, mem = 98780 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 98780 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 98784 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 98784 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 98784 KiB, score = 10
    Accepted, time = 39 ms, mem = 98788 KiB, score = 100

  • 0
    @ 2015-04-07 20:31:53

    java过不了还是怎么的?我程序一点错都没啊。。。我把这题数据翻出来,每个地方都对的。。。是不是最后一个标号后面要打空格,怎么都试了。
    真给跪了

  • 0
    @ 2014-10-16 23:38:24

    写了一个拓扑排序的题解,欢迎交流.
    http://blog.csdn.net/harlow_cheng/article/details/39932059

  • 0
    @ 2014-10-15 20:56:16

    弄了一天 终于AC了 之前是看了楼下的说用Floyed做第二问就超时了 虽然不敢说一定是Floyed的问题但是劝大家最好不要用吧 我是先用Tarjan处理第一问(要注意必须是两个人以上才能成为天使 所以答案要减掉单个人的) 再深搜第二问 最好是缩点之后再深搜吧

  • 0
    @ 2013-08-25 22:19:42

    其实这题的判断不需要dfs或者floyd,有一个我自创的定理。由于本人比较懒,一大堆定理、证明就不想打了。
    吐槽一下,这题确实有歧义,坑的我从“和”改成“或”,又从“或”改成“和”,最后翻数据才晓得是“和”。
    orz。。。。。。。

    • @ 2013-08-25 22:20:20

      加QQ1520442802

  • 0
    @ 2013-08-25 22:19:42

    其实这题的判断不需要dfs或者floyd,有一个我自创的定理。由于本人比较懒,一大堆定理、证明就不想打了。
    吐槽一下,这题确实有歧义,坑的我从“和”改成“或”,又从“或”改成“和”,最后翻数据才晓得是“和”。
    orz。。。。。。。

  • 0
    @ 2012-08-02 10:02:06

    果然还是一次就A了

    题目不难

    裸的tarjan+n次dfs可0ms

信息

ID
1626
难度
6
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
1614
已通过
439
通过率
27%
被复制
1
上传者