一个疑问
查看原帖
一个疑问
933814
QBW1117楼主2024/6/2 18:59

我改了一处宏定义,就对了,但我觉得二者没有实质性区别,求大佬

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<<" "; 
}


2024/6/2 18:59
加载中...