经典没读懂题瞎推一波样例求不出来安详入睡
题意
无向图，n个点，n个边，求图中任意一个点到另一个点的不重复路径总数。拿下图举例:
【1，2，3，4】和【1，2，4，3】是不重复的两条路径。而【1，2，3，4】和【4，3，2，1】重复了。
n个点的树有n-1条边,若再加一条边，则会形成一个环，除了环之外，其余部分由若干子树构成。 ==> 基环树。
对于无向图，拓扑排序处理出环，再处理出环上每个节点分支上的的节点个数。
设 ans=n*(n-1) ,这是所有节点都在环上的情况，每个节点到另一个节点有两条路径。
如果环上某个节点分支上有若干个节点，那么这个分支上的路径数实际是重复的，设 cnt 为环上某个节点分支上的节点总数，则重复路径数为 C2cnt ，asn 减去重复路径数即为总路径数。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int inf =0x3f3f3f3f; 5 const int qs=2e5+7; 6 vector<ll> v[qs]; 7 ll t,n,in[qs]; 8 bool u[qs]; 9 void topsort(){ //拓扑排序处理环 10 queue<ll> q; 11 for(int i=1;i<=n;++i) if(in[i]==1) q.push(i); 12 while(q.size()){ 13 ll t=q.front(); q.pop(); 14 u[t]=1; 15 int Si=v[t].size(); 16 for(int i=0;i<Si;++i){ 17 int x=v[t][i]; 18 if(in[x]>1){ 19 in[x]--; 20 if(in[x]==1) q.push(x); 21 } 22 } 23 } 24 } 25 ll dfs(int x,int fa){ //dfs求环上节点分支上节点总数 26 ll Si=v[x].size(),res=0; 27 for(int i=0;i<Si;++i){ 28 ll fx=v[x][i]; 29 if(u[fx]&&fx!=fa){ 30 res+=dfs(fx,x); 31 res++; 32 } 33 } 34 return res; 35 } 36 ll cal(ll x){ // 排列组合 去重 37 return x*(x-1)/2; 38 } 39 int main(){ 40 std::ios::sync_with_stdio(false); 41 cin>>t; 42 while(t--){ 43 cin>>n; 44 for(int i=0;i<=n;++i){ 45 v[i].clear(); in[i]=u[i]=0; 46 } 47 int x,y; 48 for(int i=1;i<=n;++i){ 49 cin>>x>>y; 50 v[x].push_back(y); in[x]++; 51 v[y].push_back(x); in[y]++; 52 } 53 topsort(); 54 ll ans=n*(n-1); //最好情况下的总路径数 55 for(int i=1;i<=n;++i){ 56 if(!u[i]){ 57 ll cnt=dfs(i,0); 58 ans-=cal(cnt+1); //去重 59 } 60 } 61 cout<<ans<<" "; 62 } 63 return 0; 64 }