首页 > 代码库 > Gym - 101334C 3514 无向仙人掌
Gym - 101334C 3514 无向仙人掌
http://codeforces.com/gym/101334/attachments
题意：
判断是否是仙人掌图并且连通，如果是的话则计算出它有多少个连通子图也是仙人掌。
思路：
连通子图也就是我们要考虑哪些边是可以删的，因为要考虑连通，那么只能删环上的边，而且一个环只能删一条边，删多了就不连通了。
那么对于每个环，它有多少条边，我们就有多少种删法，因为每个环都是独立的，那么计算数量就是要利用乘法原理。
我们要做的就是计算出每个环的边数和判断是否连通。
这个用相对时间戳来做，也就是dfn【v】=dfn【u】+1，成环的判断条件还是一样的，dfn【v】<dfn【u】。这种做法的话就可以在找环的时候计算出了边数。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 using namespace std; 12 typedef long long ll; 13 typedef pair<int,int> pll; 14 const int INF=0x3f3f3f3f3f; 15 const int maxn=20000+5; 16 17 vector<int> G[maxn]; 18 19 int n,m; 20 int cycle_num; 21 int c[maxn],dfn[maxn]; 22 int cycle[maxn]; 23 int ans[maxn]; 24 25 void dfs(int u,int fa) 26 { 27 for(int i=0;i<G[u].size();i++) 28 { 29 int v=G[u][i]; 30 if(v==fa) continue; 31 if(!dfn[v]) 32 { 33 dfn[v]=dfn[u]+1; 34 dfs(v,u); 35 c[u]+=c[v]; 36 } 37 else if(dfn[v]<dfn[u]) 38 { 39 cycle[cycle_num++]=dfn[u]-dfn[v]+2; 40 c[u]++; 41 c[v]--; 42 } 43 } 44 } 45 46 void cacl_num() 47 { 48 int len=0; 49 ans[len]=1; 50 for(int i=0;i<cycle_num;i++) 51 { 52 for(int j=0;j<=len;j++) 53 ans[j]*=cycle[i]; 54 for(int j=0;j<=len;j++) 55 { 56 ans[j+1]+=ans[j]/10; 57 ans[j]%=10; 58 } 59 while(ans[len+1]) 60 { 61 ans[len+2]=ans[len+1]/10; 62 ans[++len]%=10; 63 } 64 } 65 for(int i=len;i>=0;i--) 66 printf("%d",ans[i]); 67 68 } 69 70 void solve() 71 { 72 memset(c,0,sizeof(c)); 73 memset(ans,0,sizeof(ans)); 74 memset(dfn,0,sizeof(dfn)); 75 memset(cycle,0,sizeof(cycle)); 76 cycle_num=0; 77 dfn[1]=1; 78 dfs(1,-1); 79 for(int i=1;i<=n;i++) 80 { 81 if(dfn[i]==0||c[i]>1) 82 { 83 puts("0"); 84 return; 85 } 86 } 87 cacl_num(); 88 } 89 90 int main() { 91 freopen("cactus.in","r",stdin); 92 freopen("cactus.out","w",stdout); 93 //freopen("D:\\input.txt","r",stdin); 94 int kas=0; 95 while(~scanf("%d%d",&n,&m)) 96 { 97 for(int i=1;i<=n;i++) G[i].clear(); 98 if(kas++) puts(""); 99 100 while(m--)101 {102 int u,v,k;103 scanf("%d",&k); k--;104 scanf("%d",&u);105 while(k--)106 {107 scanf("%d",&v);108 G[u].push_back(v);109 G[v].push_back(u);110 u=v;111 }112 }113 114 solve();115 }116 return 0;117 }
Gym - 101334C 3514 无向仙人掌
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。