链式前向星改成vector后就对了(32—>100)为什么???
查看原帖
链式前向星改成vector后就对了(32—>100)为什么???
602697
wsy666楼主2023/7/27 19:14

32分代码是这样的然后就g了,但是用vector存后就对了,为什么(蒟蒻求助大佬QWQ)

#include<bits/stdc++.h>
using namespace std;
#define N 25000
#define M 1000005
struct Node{
	int to,nxt;
}edge[M];
int h[N],idx=0;
int n,m;
void add(int a,int b)
{
	edge[++idx].to=b;edge[idx].nxt=h[a];h[a]=idx;
}
int dfn[N],low[N],ti;
bool vis[N],cut[N];
void tarjan(int x,int anc)
{
	dfn[x]=low[x]=++ti;
	int child=0;
	for(int i=h[x];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(!dfn[v]){
			tarjan(v,anc);
			low[x]=min(low[x],low[v]);
			if(low[v]>=dfn[x]&&x!=anc) cut[x]=true;
			if(x==anc) child++;
		}
		else
		{
			low[x]=min(low[x],low[v]);
		}
	}
	if(child>=2&&x==anc) cut[x]=true;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
	int ans=0;
	for(int i=1;i<=n;i++) if(cut[i]) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
	return 0;
}
2023/7/27 19:14
加载中...