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?≤?19,?0?≤?m) – respectively the number of vertices and edges of the graph. Each of the subsequent?mlines contains two integers?a?and?b, (1?≤?a,?b?≤?n,?a?≠?b) indicating that vertices?aand?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.
Example
4 6
1 2
1 3
1 4
2 3
2 4
3 4
7
Note
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.
?1-2-3 2-3-4 1-3-4 1-2-4 1-2-3-4 1-2-4-3 1-4-2-3
題意:給出一個圖的點數和邊數輸出這個圖中有幾個環.
題解:這道題可以很容易想到狀壓,因為數據也只有19(orz).用sta的二進制表示已經有幾個點在這個狀態中,那怎么表示形成環呢?只需要找到一個當前狀態中的點,它神奇的與前面的某一個點有一條邊連著,那么說明肯定能構成環,可以為總答案做貢獻.如果不能,那么就為下一個狀態提供個數.不過由于是無向圖.所以兩個點也會被認為成環(兩個點構成環的個數為邊數),并且每個更大的環都會被計算兩次,所以最后要減掉.然后就搞定了.
?
代碼:
?
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std;long long dp[1<<20][20],ans=0; vector<int> e[20];int lowbit(int x) {return x&(-x); }int main() {int n,m,f,t;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d",&f,&t);e[f-1].push_back(t-1);e[t-1].push_back(f-1);}for(int i=0;i<n;i++){dp[1<<i][i]=1;}for(int sta=1;sta<(1<<n);sta++){for(int i=0;i<n;i++){if(dp[sta][i]){for(int k=0;k<e[i].size();k++){int j=e[i][k];if(lowbit(sta)>(1<<j)){continue;}if(sta&(1<<j)){if(lowbit(sta)==(1<<j)){ans+=dp[sta][i];}}else{dp[sta|(1<<j)][j]+=dp[sta][i]; }}}}ans=(ans-m)/2;printf("%lld\n",ans);return 0; }
?
?
?
?
?每天刷題,身體棒棒!
?
)
