Codeforces Round #686 (Div. 3) E Number of Simple Paths 题解

Description

题目链接
给顶一个n个顶点、n条边的图，统计图内简单路径的数量。

Solution

数据很有特点， 个顶点并且具有 条边。如果是 条边的话显然是一棵树。
树上简单路径如何计算呢? 假设当前树的节点有 个，显然是
现在多了一条边，可以看成是多棵树相互独立，中间是一个环，如下图：

由红圈中三个子树构成，分别拥有节点个数为3、3、3
对于每个子树我们统计节点数 ，可以计算贡献
那么剩下的就是如何统计节点了，类似于拓扑排序，每次把度为1的点都放到队列里，慢慢删边即可。
时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
set<int> G[N];
ll vis[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T; cin >> T;
  while(T--) {
    int n; cin >> n;
    for(int i = 1; i <= n; i++) G[i].clear(), vis[i] = 1;
    for(int i = 1; i <= n; i++) {
      int u, v; cin >> u >> v;
      G[u].insert(v);
      G[v].insert(u);
    }
    queue<int> q;
    for(int i = 1; i <= n; i++) {
      if(G[i].size() == 1) {
        q.push(i);
        vis[i] = 1;
      }
    }
    while(!q.empty()) {
      int u = q.front(); q.pop();
      for(auto &v : G[u]) {
        vis[v] += vis[u];
        vis[u] = 0;
        G[v].erase(u);
        if(G[v].size() == 1) {
          q.push(v);
        }
      }
    }  
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
      ans += (vis[i] - 1) * vis[i] / 2;
      ans += vis[i] * (n - vis[i]);
    } 
    cout << ans << '\n';
  }  
  return 0;
}