Codeforces-1454E Number of Simple Paths（基环树-思维）

Codeforces-1454E Number of Simple Paths（基环树-思维）

题目大意：

给你n个点，n条边，求图中简单路径的个数

题目思路：

n个点n条边，那么图中一定有一个环

拿这个图来讲，我们将两点间的关系分为4种1.两点都在环上，简单路径的个数为2 （例如2与5） 2.一个点在环上一个点不在环上，简单路径个数为2 （例如2与6） – 但不能是2与3或者2与4（这是情况3） 3.两个点在同一子树下（以环为根） 简单路径个数为 1 （例如2与3或者3与1） 4.两个点在不同一子树下（以环为根） 简单路径个数为 2 （例如7与3）

可以发现，任意两点间的简单路径的个数要么为1要么为2 且2的情况居多 那么可以假设4种情况都为2,只需要把情况三的算出来然后减去就行了

ans = (n-1)*n - (k-1)*k/2;k为以环上任意子节点为根的子树总节点数数学符号不会用（逃）

Code：

void top_sort() { cnt=0; queueq; mst(vis,0); mst(vi,0); for(int i=1 ; i<=n ; i++) if(d[i]==1) q.push(i); while(q.size()) { int dian = q.front(); q.pop(); vi[dian] = 1; for(int v:e[dian]) { d[v]--; if(d[v]==1) q.push(v); } } rep(i,1,n) if(vi[i]==0) huan[++cnt] = i,vis[i] = 1;}void dfs(int u,int p) { for(int v:e[u]) { if(v==p||vis[v]) continue; dfs(v,u); s[p]+=s[v]; }}int main() { int _= read(); while(_--) { n=read(),mst(d,0); rep(i,1,n) e[i].clear(),s[i] =1; for(int i=1 ; i<=n ; i++) { int u,v; u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); d[u]++,d[v]++; } top_sort(); ll ans = (n-1)*n*1ll; for(int i=1 ; i<=cnt; i++) { int u = huan[i]; dfs(u,u); ans -=(s[u]-1)*s[u]/2ll; } printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。