链接：https://ac.nowcoder.com/acm/problem/50412 来源：牛客网
题目描述
Byteotia城市有n个城镇，m条双向道路。每条道路连接两个不同的城镇，没有重复的道路，所有城镇连通。 输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
输入描述
输入n,m及m条边。
输出描述
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
分析
tarjan判断割点，和蓝书上面的BLO有点类似，区别就是BLO是去边，这里是去点
首先我们可以判断，如果一个点是不是割点，那么即使这个点去除，也不会影响整张图的连通性，所以仅仅是被删除的点和其他点不能进行连接，答案为2 * (n - 1)
如果一个点是割点的话，那么去掉这个点就可以把这张图分成几个树形结构，任意两个树形结构之间不能进行连接，所以我们只需要求树的大小即可
代码
#include <cstring>
#include <iostream>
using namespace std
;
typedef long long ll
;
const int N
= 1e5 + 10, M
= 1e6 + 10;
int n
,m
;
int h
[N
],ne
[M
],e
[M
],idx
;
int dfn
[N
],low
[N
],ti
;
int root
;
ll ans
[N
];
ll Size
[N
];
bool st
[N
];
void add(int x
,int y
){
e
[idx
] = y
,ne
[idx
] = h
[x
],h
[x
] = idx
++;
}
void tarjan(int u
){
dfn
[u
] = low
[u
] = ++ti
;
int cnt
= 0;
Size
[u
] = 1;
ll sum
= 0;
for(int i
= h
[u
];~i
;i
= ne
[i
]){
int j
= e
[i
];
if(!dfn
[j
]){
tarjan(j
);
Size
[u
] += Size
[j
];
low
[u
] = min(low
[u
],low
[j
]);
if(low
[j
] >= dfn
[u
]){
cnt
++;
sum
+= Size
[j
];
if(u
!= root
|| cnt
> 1) st
[u
] = true;
ans
[u
] += Size
[j
] * (n
- Size
[j
]);
}
}
else low
[u
] = min(low
[u
], dfn
[j
]);
}
if(!st
[u
]) ans
[u
] = 2 * (n
- 1);
else ans
[u
] += 1ll * (n
- 1) + (n
- 1 - sum
) * (sum
+ 1);
}
int main(){
scanf("%d%d",&n
,&m
);
memset(h
,-1,sizeof h
);
while(m
--){
int a
,b
;
scanf("%d%d",&a
,&b
);
add(a
,b
),add(b
,a
);
}
for(root
= 0;root
< n
;root
++)
if(!dfn
[root
])
tarjan(root
);
for(int i
= 1;i
<= n
;i
++)
printf("%lld\n",ans
[i
]);
return 0;
}
