Online Judge:#uoj 67 http://uoj.ac/problem/67
Label:Tarjan, 割点, 细节
题目描述
辞旧迎新之际, 喜羊羊正在打理羊村的绿化带, 然后他发现了一棵长着毒瘤的树. 这个长着毒瘤的树可以用 \(n\)个结点 \(m\)条无向边的无向图表示. 这个图中有一些结点被称作是毒瘤结点, 即删掉这个结点和与之相邻的边之后, 这个图会变为一棵树. 树也即无简单环的无向连通图.
现在给你这个无向图, 喜羊羊请你帮他求出所有毒瘤结点.
输入
第一行两个正整数 \(n,m\), 表示有 \(n\)个点 \(m\)条边. 保证 \(n≥2\).
接下来 \(m\)行, 每行两个整数 \(v,u\), 表示 \(v\)和 \(u\)之间有一条无向边.\(1≤v,u≤n\). 保证没有重边和自环.
输出
第一行一个正整数 \(n_s\), 表示这个图中有 \(n_s\)个结点是毒瘤.
接下来一行, 共 \(ns\)个整数, 每个整数表示一个毒瘤结点的编号. 请按编号从小到大的顺序输出.
数据保证图中至少存在一个毒瘤结点.
样例
- Input#1
- 6 6
- 1 2
- 1 3
- 2 4
- 2 5
- 4 6
- 5 6
- Output#1
- 3 4 5 6
- Hint
对于 40% 数据,\(n,m<=1000\);
另存在 10% 数据,\(m=n-1\);
另存在 20% 数据,\(m=n\);
对于 100% 数据,\(n,m<=10^5\).
题解
删掉毒瘤后, 变成一棵树. 所以这个毒瘤显然不能是割点, 删去一个毒瘤, 剩下 \(n-1\)个点, 既然是一棵树, 也就是说还剩 \(n-2\)条边, 那么还需满足一个条件, 毒瘤的度为 \(m-(n-2)=m-n+2\).
这道题就变成了裸的 Tarjan 求割点板子 + 特判, 割点板子在此:) https://www.luogu.org/problem/P3388 .
1. 对于根节点, 只需满足它的儿子数>=2, 它就是割点.
2. 对于非根节点 x, 只需他存在一个儿子 y 满足 \(low[y]>=dfn[x]\),x 就是割点.
但这题还有几个毒瘤细节. 题目说了, 数据保证至少存在一个毒瘤, 所以大致可以知道数据形成的图是什么样子, 显然, 存在的联通块数量 <=2. 而且当联通块数量为 2 时, 有一个联通块只包含一个点, 并且此时 \(m=n-2\), 按理说这种情况应该特判一下的(答案就是唯一的那个点), 但好像不去判也没关系, 就不管它了. 剩下的情况都是一个联通块的, 所以直接 tarjan(1,0) 就好了, 不用扫一遍 for(i=1~n)if(!dfn[i])tarjan(i,0)这样了.
代码如下:
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e5+10;
- inline int read(){
- int x=0;char c=getchar();
- while(!isdigit(c))c=getchar();
- while(isdigit(c))x=x*10+c-'0',c=getchar();
- return x;
- }
- struct edge{
- int to,nxt;
- }e[N<<1];
- int n,m,ing[N],dfn[N],low[N],ge[N];
- int ecnt,head[N];
- inline void link(int u,int v){
- e[++ecnt].to=v,e[ecnt].nxt=head[u];
- head[u]=ecnt;
- }
- int tot,rootson;
- vector<int>ans;
- void tarjan(int x,int fa){
- dfn[x]=low[x]=++tot;
- for(int i=head[x];i;i=e[i].nxt){
- int y=e[i].to;
- if(!dfn[y]){
- if(fa==0)rootson++;
- tarjan(y,x);
- low[x]=min(low[x],low[y]);
- if(fa!=0&&low[y]>=dfn[x])ge[x]=1;
- }
- else{low[x]=min(low[x],dfn[y]);}
- }
- if(fa==0&&rootson>=2)ge[x]=1;
- }
- int main(){
- n=read(),m=read();
- for(int i=1;i<=m;i++){
- int u=read(),v=read();
- link(u,v);link(v,u);
- ing[u]++,ing[v]++;
- }
- tarjan(1,0);
- for(int i=1;i<=n;i++)if(ing[i]==m-n+2&&!ge[i])ans.push_back(i);
- printf("%d\n",ans.size());
- for(int i=0;i<ans.size();i++)printf("%d",ans[i]);
- }
UOJ67 新年的毒瘤[Tarjan, 割点]
来源: http://www.bubuko.com/infodetail-3258822.html