首页 > 代码库 > Gym 101334C 无向仙人掌
Gym 101334C 无向仙人掌
给出图，求他的“仙人掌度”，即求包括他自身的生成子图有多少？
只能删去仙人掌上的叶子的一条边，然后根据乘法原理相乘；
1、怎么求一个仙人掌叶子上有多少边？ 可以利用点，边双连通的时间戳这个概念，但是绝对时间是不对的，只能用相对的时间戳。
2、怎么把第二种情况剔除掉？ 就是记录每一个点加入环中的次数；
3、第三种情况，就是判连通了；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 20000 + 5; 6 7 struct Sol { 8 vector<int> G[maxn]; 9 int cyclecnt; 10 int cycle[maxn]; 11 int dfn[maxn]; 12 int c[maxn]; 13 int n; 14 int num[maxn]; 15 16 void init(int n) { 17 this->n = n; 18 for(int i=0; i<=n; i++) 19 G[i].clear(); 20 memset(dfn,0,sizeof(dfn)); 21 memset(cycle,0,sizeof(cycle)); 22 memset(num,0,sizeof(num)); 23 cyclecnt = 0; 24 dfn[1] = 1; 25 } 26 27 void AddEdge (int from,int to) { 28 G[from].push_back(to); 29 G[to].push_back(from); 30 } 31 32 void dfs(int u,int fa) { 33 for(int i=0; i<G[u].size(); i++) { 34 int v = G[u][i]; 35 if(v==fa) continue; 36 37 if(!dfn[v]) { 38 dfn[v] = dfn[u] + 1; 39 dfs(v,u); 40 c[u]+=c[v]; 41 } else if(dfn[v]<dfn[u]) { 42 cycle[cyclecnt++] = dfn[u] - dfn[v] + 2; 43 c[u]++; 44 c[v]--; 45 } 46 } 47 } 48 49 void ans() { 50 for(int i=1; i<=n; i++) 51 if(c[i]>1||dfn[i]==0) { 52 puts("0"); 53 return; 54 } 55 //int res = 1; 56 //for(int i=0;i<cyclecnt;i++) 57 // res = res * cycle[i]; 58 //return res; 59 60 int len = 0; 61 num[0] = 1; 62 63 for(int i=0; i<cyclecnt; i++) { 64 65 for(int j=0; j<=len; j++) 66 num[j] = num[j]*cycle[i]; 67 68 for(int j=0; j<=len; j++) { 69 num[j+1] += num[j]/10; 70 num[j] = num[j]%10; 71 } 72 while(num[len+1]) { 73 num[len+2]+=num[len+1]/10; 74 num[++len]%=10; 75 } 76 } 77 78 for(int i=len; i>=0; i--) 79 printf("%d",num[i]); 80 puts(""); 81 } 82 83 84 85 } sol; 86 87 int main() { 88 freopen("cactus.in","r",stdin); 89 freopen("cactus.out","w",stdout); 90 int n,m; 91 scanf("%d%d",&n,&m); 92 93 sol.init(n); 94 95 for(int i=0; i<m; i++) { 96 int k,u; 97 scanf("%d%d",&k,&u); 98 for(int i=0; i<k-1; i++) { 99 int v;100 scanf("%d",&v);101 sol.AddEdge(u,v);102 u = v;103 }104 }105 106 sol.dfs(1,-1);107 108 sol.ans();109 110 //printf("%d\n",sol.ans());111 112 return 0;113 }
Gym 101334C 无向仙人掌
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。