首页 > ACM题库 > HDU-杭电 > HDU 3964-Find The Simple Circle-图-[解题报告]HOJ
2015
04-14

HDU 3964-Find The Simple Circle-图-[解题报告]HOJ

Find The Simple Circle

问题描述 :

Given a directed graph, your task is to find the simple circles. The simple circle is a subgraph meeting the following conditions:

1. There are m ( m > 1 ) different vertexes and arcs in it.

2. The simple circle can be represented as a seqence "v1,v2…vm" and v1,v2…vm are different vertexes in it. There is an arc from the i-th vertex to the (i+1)-th vertex or from the m-th vertex to the 1st vertex in the simple circle.

You will be given the adjacency matrix of the directed graph, what you should do is outputing all the simple circles in it in lexicographic order. The output format of one simple circle is a string where the i-th character is the index of the i-th vertex in the simple circle seqence. To unify the format, the 1st vertex should be the vertex with smallest index. Vertexes are indexed from 0. A sequence a1,a2…ak appears in lexicographic order before a sequence b1,b2…bk if and only if the first ai, which is different from bi, is less than bi.

输入:

There are several test cases in the input. Each case begins with a line with an integer N (2 ≤ N ≤ 9), denoting the number of vertexes in the graph. In the following N lines with N integers, the j-th number in the i-th line will be 1 or 0, representing that there is an arc from the i-th vertex to the j-th vertex or not. It is ensured that the i-th number in the i-th line is 0. Input is terminated by EOF.

输出:

There are several test cases in the input. Each case begins with a line with an integer N (2 ≤ N ≤ 9), denoting the number of vertexes in the graph. In the following N lines with N integers, the j-th number in the i-th line will be 1 or 0, representing that there is an arc from the i-th vertex to the j-th vertex or not. It is ensured that the i-th number in the i-th line is 0. Input is terminated by EOF.

样例输入:

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

样例输出:

01
012
02
021
12

01
012
0123
03
032
23

	/*
	在一个有向图中找出所有的环,按字典序输出
	解法:以每个点为起点dfs,搜索u->v时如果v是已经访问的点,那么必然有v->u->v的环
	一直在纠结怎么排序,怎么判重。
	其实,在搜索点i后,ins[i]不清空标记就行了,因为如果后续有环经过i,那么这个环必然是重复的(从i搜索的时候必然可以搜索到)。
	*/
	#include<iostream>  
    #include<cstdio>  
    #include<cstring>  
    #include<cmath>  
    #include<algorithm>  
    #include<queue>  
    #include<vector>  
    #include<set>
    #include<stack>  
    #include<map>  
    #define MAX 12  // 点的最大数量  
    #define MAXE 200// 边的最大数量  
    using namespace std;  
    int g[MAX][MAX];
    int ins[MAX];// 是否在栈中  
    int n;  
    int s[MAX];  
    int snum;
    int index=1;
    int DFS(int x)  
    {   
        s[snum++]=x;
        for(int i=0;i<n;i++)if(g[x][i])
        {
            if(ins[i]&&i==index)
            {
                for(int i=0;i<snum;i++)
                printf("%d",s[i]);
                printf("\n");
            }
            else if(!ins[i])
            {
                ins[i]=1;
                DFS(i);
                ins[i]=0;
                snum--;
            }
        }
        return 1;
    }  
    void solve()  
    {  
        for(int i=0;i<n;i++)  
        {  

            snum=0;
            index=i;
            ins[i]=1;
            DFS(i);
        }  
    }  
    void init()  
    {  
       while(scanf("%d",&n)!=EOF)
       { 
        memset(ins,0,sizeof(ins));
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {  
          scanf("%d",&g[i][j]);
        } 
        solve(); 
        puts("");
      }
    }  
    
    
    int main()  
    {  
       
            init();  
    return 0;  
    }      

版权声明:本文为博主原创文章,未经博主允许不得转载。

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


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?