CodeForces - 1454E Number of Simple Paths(基环树+思维)

题目链接：点击查看

题目大意：给出一棵 n 个点的基环树，现在需要求所有长度大于等于 1 的路径个数

题目分析：对于所有的路径 ( x , y ) 可以分成下列两种情况来考虑：

路径不会经过环上的边：此时点 x 和点 y 之间的路径是唯一的

路径会经过环上的边：此时点 x 和点 y 之间的路径有两条，一条是沿着环顺时针走，另一条是沿着环逆时针走

当然直接正向去考虑应该也是可以做出来的，但这个题比较优秀的一种思路是正难则反，首先假设所有的路径都会经过环上的边，然后再统计有多少个点对 ( x , y ) 之间的路径是无需经过环上的边，减去其贡献即可

具体实现是先跑出环，这个用拓扑或dfs都能跑，然后将整个环视为根节点，这样整张图就可以视为一棵树了，跑出以环为 “根” 节点的所有子树大小即可，因为对于每个子树来说都是相互独立的，每个子树中的点两两之间必定只有唯一的一条路径

代码：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;vector<int>node[N];bool vis[N];int fa[N],dfn[N],id;void get_loop(int u) {dfn[u]=++id;for(auto v:node[u]){if(dfn[v]){if(dfn[v]<dfn[u])continue;while(v!=fa[u]){vis[v]=true;v=fa[v];}return;}fa[v]=u;get_loop(v);} }int dfs(int u) {vis[u]=true;int ans=1;for(auto v:node[u]){if(vis[v])continue;ans+=dfs(v);}return ans; }void init(int n) {id=0;for(int i=1;i<=n;i++)node[i].clear();memset(dfn,0,sizeof(int)*(n+5));memset(vis,false,n+5); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);init(n);for(int i=1;i<=n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}get_loop(1);LL ans=1LL*n*(n-1);for(int i=1;i<=n;i++)if(vis[i]){LL t=dfs(i);ans-=t*(t-1)/2;}printf("%lld\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1454E Number of Simple Paths(基环树+思维)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。