< 题目链接 >
题目大意:
现在给定一张连通的无向图, 不包含重边. 现在输出 $n$ 个整数, 表示将第 $i$ 个节点的所有与其它节点相关联的边去掉之后 (不去掉 $i$ 节点本身), 无向图中有多少个有序对 $(u,v)$, 满足 $u,v$ 不连通.
解题分析:
首先, 很明显,$i$ 节点是需要分成割点和非割点来进行讨论的.
对于非割点 i 来说, 去除 $i$ 周围的所有边之后, 只有 $i$ 点和其它 $n-1$ 个点不连通, 所以增加的有序对为 $2*(n-1)$ 个.
对于割点 $i$ 来说, 假设在搜索树上, 节点 i 有 $t$ 个子树, 则至多能够够分成 $t+2$ 个连通块, 每个连通块的节点构成情况为:
1. 节点 $i$ 独自构成一个连通块
2. 有 $t$ 个连通块, 分别由搜索树上 $i$ 的 $t$ 个子树的所有节点分别构成
3. 还有除上述所有节点之外的点构成 (比如在搜索树上,$i$ 节点父亲方向的所有节点)
割点有序对的所有情况就能够依据上面几种情况求出, 这里就不再进行赘述.
割点的判定法则:
u 是割点当且仅当搜索树上存在的一个子节点 v, 满足:$$low[v]>=dfn[u]$$
特别地, 如果 u 是搜索树上的根节点, 则 u 是割点当且仅当存在至少两个子节点满足上述条件.
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 1e5+5, M = 5e5+5;
- struct Edge{
- int to,nxt;
- }edge[M<<1];
- int n,m,cnt,tot,head[N],dfn[N],low[N],sz[N];
- bool cut[N];
- ll ans[N];
- void addedge(int u,int v){
- edge[++cnt].to=v,edge[cnt].nxt=head[u];
- head[u]=cnt;
- }
- void Tarjan(int u){
- dfn[u]=low[u]=++tot;sz[u]=1;
- int flag=0,sum=0;
- for(int i=head[u];i;i=edge[i].nxt){
- int v=edge[i].to;
- if(!dfn[v]){
- Tarjan(v);
- sz[u]+=sz[v];
- low[u]=min(low[u],low[v]);
- if(low[v]>=dfn[u]){ // 如果满足割点的条件
- flag++;
- ans[u]+=(ll)(sz[v])*(n-sz[v]); //v 所在的连通分量与其它所有点构成的有序对数量
- sum+=sz[v];
- if(u!=1 || flag>1)cut[u]=true;
- }
- }else low[u]=min(low[u],dfn[v]);
- }
- if(cut[u])ans[u]+=(ll)(sum+1)*(n-sum-1)+(n-1); // 父亲方向的点与其它点构成的有序对 以及 i 节点独自与其它节点构成的有序对
- else ans[u]=2*(n-1);
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int u,v;scanf("%d%d",&u,&v);
- addedge(u,v);addedge(v,u);
- }
- Tarjan(1); // 因为这是无向图, 并且所有的点连通
- for(int i=1;i<=n;i++)
- printf("%lld\n",ans[i]);
- }
- 2019-03-01
来源: http://www.bubuko.com/infodetail-2972188.html