我改了一处宏定义,就对了,但我觉得二者没有实质性区别,求大佬
RE 0pts:
#include <bits/stdc++.h>
#define f(i,a,b) for(int i = a ; i<=b ; i++)
#define N 200005
using namespace std;
int n,m,ans,x,y;
//题目
vector<int> G[N];
int dfn[N],low[N];//dfn访问次序(时间戳,第几个节点进入)
//low:某点可通过回溯到达的最早的点的时间戳,回溯即意味着不能走来时的路,
//也就意味着走不通过父亲的路
//已遍历点:u所在图中时间戳小于等于u的点。
bool is_cut[N];//是否是割点
int dfs_clock;//当前时间
void tarjan(int x,int root){
dfs_clock++;
dfn[x] = dfs_clock;
low[x] = dfs_clock;
int chd = 0;//所在局部的根节点分叉数量(只有局部的)
//访问x的孩子
f(i,0,G[x].size()-1){//!!!!!!!疑问点
int v = G[x][i];//x-->v
if(!dfn[v]){
tarjan(v,root);
low[x] = min(low[x],low[v]);//v能到,x也能到,更新
if (low[v]>=dfn[x] && x!=root) is_cut[x]=true;
/*表示儿子 v点回溯可到达的最先点的时间戳大于等于u的时间戳,
证明其不能通过 u以外的点与已遍历点相连,那么意味着必然可以通过割去u而
使得已遍历点与儿子
v 位于两个不互相连通的图。*/
if (x == root) chd++;
//遍历过,直接更新
}
else low[x] = min(low[x],dfn[v]);
}
if(x == root && chd>=2) is_cut[x]=true;
//对于这一种割点,显然,两个子树只有根这么一条路。不过对于其儿子个数的判断,
//由于根可能会有几个儿子位于割去根后的同一个团中,而访问其中一个就可以通过遍历使这几个儿子的 dfn
//都有值。所以只有当根扫到的儿子未被访问过时,才会有 child 的值加一。
}
int main(){
cin>>n>>m;
f(i,1,m){
cin>>x>>y;
G[x].push_back(y) ;
G[y].push_back(x);
}
f(i,1,n) if(!dfn[i]) tarjan(i,i);
f(i,1,n) if(is_cut[i]) ans++;
cout<<ans<<"\n";
f(i,1,n) if(is_cut[i]) cout<<i<<" ";
}
AC 100pts Code:
#include <bits/stdc++.h>
#define f(i,a,b) for(int i = a ; i<=b ; i++)
#define F(i,a,b) for(int i = a ; i<b ; i++)//修改
#define N 200005
using namespace std;
int n,m,ans,x,y;
//题目
vector<int> G[N];
int dfn[N],low[N];//dfn访问次序(时间戳,第几个节点进入)
//low:某点可通过回溯到达的最早的点的时间戳,回溯即意味着不能走来时的路,
//也就意味着走不通过父亲的路
//已遍历点:u所在图中时间戳小于等于u的点。
bool is_cut[N];//是否是割点
int dfs_clock;//当前时间
void tarjan(int x,int root){
dfs_clock++;
dfn[x] = dfs_clock;
low[x] = dfs_clock;
int chd = 0;//所在局部的根节点分叉数量(只有局部的)
//访问x的孩子
F(i,0,G[x].size()){//!!!!
int v = G[x][i];//x-->v
if(!dfn[v]){
tarjan(v,root);
low[x] = min(low[x],low[v]);//v能到,x也能到,更新
if (low[v]>=dfn[x] && x!=root) is_cut[x]=true;
/*表示儿子 v点回溯可到达的最先点的时间戳大于等于u的时间戳,
证明其不能通过 u以外的点与已遍历点相连,那么意味着必然可以通过割去u而
使得已遍历点与儿子
v 位于两个不互相连通的图。*/
if (x == root) chd++;
//遍历过,直接更新
}
else low[x] = min(low[x],dfn[v]);
}
if(x == root && chd>=2) is_cut[x]=true;
//对于这一种割点,显然,两个子树只有根这么一条路。不过对于其儿子个数的判断,
//由于根可能会有几个儿子位于割去根后的同一个团中,而访问其中一个就可以通过遍历使这几个儿子的 dfn
//都有值。所以只有当根扫到的儿子未被访问过时,才会有 child 的值加一。
}
int main(){
cin>>n>>m;
f(i,1,m){
cin>>x>>y;
G[x].push_back(y) ;
G[y].push_back(x);
}
f(i,1,n) if(!dfn[i]) tarjan(i,i);
f(i,1,n) if(is_cut[i]) ans++;
cout<<ans<<"\n";
f(i,1,n) if(is_cut[i]) cout<<i<<" ";
}