题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1123
就是求一求BCC
在求BCC的时候顺便统计一下答案
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; const int M = 1000000+9; int n,m,head[N],nxt[M],to[M],sz[N]; int lowlink[N],num[N],bcc_cnt,num_cnt; LL vout[N]; vector<int> bcc_num[N]; stack<int> stk; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } void Tarjan(int w, int f) { lowlink[w] = num[w] = ++num_cnt; stk.push(w); sz[w] = 1; int tmp = 0; for (int i=head[w];i;i=nxt[i]) if (to[i] != f) { if (!num[to[i]]) { Tarjan(to[i], w); sz[w] += sz[to[i]]; lowlink[w] = min(lowlink[w], lowlink[to[i]]); if (lowlink[to[i]] >= num[w]) { int cur; bcc_cnt++; do { cur = stk.top(); stk.pop(); bcc_num[cur].push_back(bcc_cnt); } while (cur != to[i]); vout[w] += 2LL * tmp * sz[to[i]]; tmp += sz[to[i]]; } } else { lowlink[w] = min(num[to[i]], lowlink[w]); } } vout[w] += 2LL * tmp * (n - tmp - 1) + 2 * (n - 1); } inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } int main(){ n = read(); m = read(); for (int i=1;i<=m;i++) { Add_Edge(read(),read()); } Tarjan(1,1); for (int i=1;i<=n;i++) { printf("%lld\n",vout[i]); } return 0; }