求简单无向图中环的个数_有向无环图最多有多少条边

求简单无向图中环的个数_有向无环图最多有多少条边QuestionD.ASimpleTasktimelimitpertest3secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputGivenasimplegraph,outputthe
Question

D. A Simple Task
time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 190 ≤ m) – respectively the number of vertices and edges of the graph. Each of the subsequent m lines contains two integers a and b, (1 ≤ a, b ≤ na ≠ b) indicating that vertices a and b are connected by an undirected edge. There is no more than one edge connecting any pair of vertices.

Output

Output the number of cycles in the given graph.

Sample test(s)
input
4 6
1 2
1 3
1 4
2 3
2 4
3 4

只听到从架构师办公室传来架构君的声音:
向露冷风清,无人处,耿耿寒漏咽。有谁来对上联或下联?
output
此代码由Java架构师必看网-架构君整理
7

Note

The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.

求简单无向图中环的个数?简单无向图即 无自环,无重边的无向图。

 这个是NP问题; codeforces 上有一题用的是状态压缩写的。

 dp[s][i] s集合里最小的点到其他点的路径数;

dp[s][i] += dp[s^(1<<i)][j](g[j][i]=true)

ans加上可以构成环的路径数.怎么才能构成环呢? 如a->b->.....->c ,如果知道ac是可达的,只要加上a,经过ab...到达c的路径数就可以了。注意a是这个集合里最小的数。而且同一个环会被记录两次,因为2条路径才是一个环。

codeforces 11D 
http://www.codeforces.com/contest/11/problem/D

code :

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef __int64 ll;
#define maxn 20
ll dp[1<<maxn][maxn]; // 注意数据
bool g[maxn][maxn];
// dp[s][i] s中最小的点到其他点路径数;
// dp[s][i] += dp[s^i][j](g[i][j] = true )

int main(){
    int n, m;
    while( cin >> n >> m ) {
        memset(g, 0, sizeof g);
        int state = (1<<n);
        for ( int i=0; i<state; ++i)
          for ( int j=0; j<n; ++j )
            dp[i][j] = 0;

        for ( int i=0, a, b; i<m; ++i ){
            scanf ("%d%d", &a, &b);
            --a, --b;
            g[a][b] = g[b][a] = true;
            dp[(1<<a)|(1<<b)][a] = dp[(1<<a)|(1<<b)][b] = 1;
        }

        ll ans = 0;
        for ( int s=1; s<state; ++s ){
             int i, j, k;
             for ( i=0; i<n && !(s&(1<<i)); ++i );
             for ( j=i+1; j<n; ++j ) if(s&(1<<j) )
             {
                 for ( k=i+1; k<n; ++k ) if(s&(1<<k)){
                      if(g[k][j] )
                        dp[s][j] += dp[s^(1<<j)][k];
                 }
                 if(g[i][j] && (s^(1<<i)^(1<<j))) // 3个点以上才行
                   ans += dp[s][j];
             }
        }
        // 枚举了环的两侧,so。。。
        cout << (ans>>1) << endl;
    }
};

转载地址:

http://www.cnblogs.com/TengXunGuanFangBlog/archive/2013/04/19/loop_problem.html

架构君码字不易,如需转载,请注明出处:https://javajgs.com/archives/166158
0
 

发表评论