首页 > ACM题库 > HDU-杭电 > HDU 3594-Cactus-图-[解题报告]HOJ
2014
11-27

HDU 3594-Cactus-图-[解题报告]HOJ

Cactus

问题描述 :

1. It is a Strongly Connected graph.
2. Each edge of the graph belongs to a circle and only belongs to one circle.
We call this graph as CACTUS.

The most powerful force

There is an example as the figure above. The left one is a cactus, but the right one isn’t. Because the edge (0, 1) in the right graph belongs to two circles as (0, 1, 3) and (0, 1, 2, 3).

输入:

The input consists of several test cases. The first line contains an integer T (1<=T<=10), representing the number of test cases.
For each case, the first line contains a integer n (1<=n<=20000), representing the number of points.
The following lines, each line has two numbers a and b, representing a single-way edge (a->b). Each case ends with (0 0).
Notice: The total number of edges does not exceed 50000.

输出:

The input consists of several test cases. The first line contains an integer T (1<=T<=10), representing the number of test cases.
For each case, the first line contains a integer n (1<=n<=20000), representing the number of points.
The following lines, each line has two numbers a and b, representing a single-way edge (a->b). Each case ends with (0 0).
Notice: The total number of edges does not exceed 50000.

样例输入:

2
4
0 1
1 2
2 0
2 3
3 2
0 0
4
0 1
1 2
2 3
3 0
1 3
0 0

样例输出:

YES
NO

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3594

题意:判断给定的有向图是否满足 1.强连通 2 每一条边属于且仅属于一个环

tarjan算法的运用,用fa[]数组记录tarjand的搜索路径,当有一个点有横向边(指向它的祖先节点——表示有环),据fa记录的路径标记 除被指向的祖先外所有路径上的点,当有某个点被记录2次时,必然存在一条边属于两个环。

#include<iostream>  
    #include<cstdio>  
    #include<cstring>  
    #include<cmath>  
    #include<algorithm>  
    #include<queue>  
    #include<vector>  
    #include<stack>  
    #include<map>  
    #define MAX 20500  // 点的最大数量  
    #define MAXE 50500// 边的最大数量  
    using namespace std;  
    // 假设对边u-->v  
    struct EDGE  
    {  
        int v; // 从u点出发能到达的点v  
        int next; // 从u点出发能到达的下一条边的编号  
    }edge[MAXE];  
    int first[MAX];   // first[u] = e:从点u出发的最后一条边的编号是e(“最后”是指最后输入)  
    int dfn[MAX];  // dfn[u]:节点u搜索的次序编号(时间戳)  
    int low[MAX];// low[u]:是u或u的子树能够追溯到的最早的栈中节点的次序号  
    int ins[MAX];// 是否在栈中  
    //int scc[MAX]; // scc[i] = j:第i个点所在的强连通分量的编号  (此题可有可无)
    int out[MAX];  
    int in[MAX];// 强连通分量的出度  
    int fa[MAX];//fa[i] 表示 i的前驱 (父亲节点)
    int n,m;  
    int num; // 强连通分量的数目  
    int index; // 次序编号  
    stack<int> s;  
    bool ok;//判断是否满足条件
    void sign(int v,int x)
    {
        while(fa[x]!=v)
        {
            out[x]++;//out[x] 表示被标记了几次
        //    cout<<x<<endl;
            if(out[x]>1)//超过2次 必定有边 同属于两个环
            {
                ok=false;
                return ;
            }
            x=fa[x];
        }
    }
    int DFS(int x)  
    {  
        if(!ok)return 0;
        low[x]=dfn[x]=index++;  
        s.push(x);  
        ins[x]=1;  
        // 枚举每一条边:u-->v  
        for(int k=first[x];k!=-1;k=edge[k].next)  
        {  
            int v=edge[k].v;  
            if(dfn[v]==0)  
            {  
                fa[v]=x;
                DFS(v);  
                low[x]=min(low[x],low[v]); 
            }  
            else if(ins[v])  
            {  
                low[x]=min(dfn[v],low[x]); 
                sign(v,x);	//由x沿路径返回并标记一直找到v
                if(ok==false)
                return 0;
            }  
        }  
         // 如果节点u是强连通分量的根  
        if(low[x]==dfn[x])  
        {  
            int v;  
            num++;  
        if(num>1){ok=false;return 0;}//出现两个强联通分量
            do{  
            v=s.top();  
            s.pop();  
            ins[v]=0;  
      //      scc[v]=num;  
            }while(v!=x);  
        }  
        return 1;
    }  
    
    void init()  
    {  
        memset(dfn,0,sizeof(dfn));  
        memset(low,0,sizeof(low));  
        memset(first,-1,sizeof(first));  
        memset(ins,0,sizeof(ins));  
        memset(out,0,sizeof(out));  
        memset(in,0,sizeof(in));  
     //   memset(scc,0,sizeof(scc));  
        index=1;  
        num=0;  
        ok=true;
        int a,b,e=0;  
        scanf("%d",&n);
        for(;;)  
        {  
            scanf("%d%d",&a,&b);
            if(a+b==0)break;    
            edge[e].v=b;  
            edge[e].next=first[a];  
            first[a]=e;  
            e++;  
        }  
      
    }  
    
    void solve()  
    {  
          // 求强连通分量  
        for(int i=0;i<n;i++)  
        {  
            if(dfn[i]==0)  
            {  
               DFS(i);
                if(ok==false)
                break;
            }  
        }  
        if(ok)
        printf("YES\n");
        else 
        printf("NO\n");
    }  
    int main()  
    {  
        int Case;
        scanf("%d",&Case);
        while(Case--)  
        {  
            init();  
            solve();  
        }  
    return 0;  
    }      

参考:http://blog.csdn.net/wsniyufang/article/details/6609872


, ,
  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确