Description
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
Input
输入n<=100000 m<=500000及m条边
Output
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
Sample Input
5 5 1 2 2 3 1 3 3 4 4 5
Sample Output
8 8 16 14 8
看到这道题，首先想到是的Tarjan先缩点。但是后来发现，如果按照DFS序搜索的话，只要DFS返回以后，判断当前点事割点，那么这个点和刚才搜索的点就是一个联通块。
然后就是对于每个割点，它的下面会有很多联通块，如果这个割点被去掉，那么下面的联通块都会被拆开。我们设ans[u]为这个点去掉后有多少点会被分离，我们在计算每个它
下面的联通块时，把它们的大小依次乘起来。然后，再加上它的下面联通块的和乘以上面所有点的和。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define MAXN 1000010
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
inline int read(){
int x=
0,f=
1;
char ch=
getchar();
for(;!isdigit(ch);ch=
getchar())
if(ch==
'-')
f=-
1;
for(;isdigit(ch);ch=
getchar())
x=x*
10+ch-
'0';
return f*
x;
}
int n,m;
int total=
0,head[MAXN],nxt[MAXN<<
4],to[MAXN<<
4],size[MAXN];
int dfn[MAXN],low[MAXN],cnt;
long long ans[MAXN<<
2];
inline void adl(
int a,
int b){
total++
;
to[total]=
b;
nxt[total]=
head[a];
head[a]=
total;
return ;
}
inline void tarjan(
int u){
dfn[u]=low[u]=++
cnt;
size[u]=
1;
int sum=
0;
for(
int e=head[u];e;e=
nxt[e]){
if(!
dfn[to[e]]){
tarjan(to[e]);
size[u]+=size[to[e]];
//size代表以u为根的联通块大小
low[u]=
min(low[u],low[to[e]]);
if(low[to[e]]>=
dfn[u]){
ans[u]+=(
long long)sum*size[to[e]];
//sum表示已经遍历的子联通块，现在发现一个新的联通块，要把它的大小乘以已经遍历的
sum+=size[to[e]];
//然后把它的大小加进去
}
}
else low[u]=
min(low[u],dfn[to[e]]);
}
ans[u]+=(
long long)sum*(n-sum-
1);//
再加上它的下面联通块的和乘以上面所有点的和。
}
int main(){
in(n);
in(m);
int a,b;
REP(i,1,m){
in(a);
in(b);
adl(a,b);
adl(b,a);
}
tarjan(1);
REP(i,1,n) printf(
"%lld\n",(ans[i]+n-
1)<<
1);//n-1是这个割点和其他点的断开，*2是因为题目里A和B还有B和A算一个。
return 0;
}
转载于:https://www.cnblogs.com/jason2003/p/9708796.html
