dfsTLE求助
  • 板块灌水区
  • 楼主羊叫兽同学
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/5/11 16:51
  • 上次更新2023/10/28 01:41:25
查看原帖
dfsTLE求助
476767
羊叫兽同学楼主2022/5/11 16:51

https://www.luogu.com.cn/problem/P3388 dfsTLE求助

#include<iostream>
using namespace std;
int dfn[100086],low[1000086],xis[1000086];
int h[100086],f[1000086],ne[1000086],v1[100086];
int times,cnt,top;
int vist[1000086];
void add(int x,int y){
v1[++top]=y;
ne[top]=h[x];
h[x]=top;
}
void dfs(int u,int father)
{
	
    dfn[u]=low[u]=++times;
    int son=0;
    for(int i=h[u];i!=0;i=ne[i])
    {
        int v=v1[i];
        if(!dfn[v])
        {
            dfs(v,father);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=father)
            xis[u]=1;
            if(u==father)
            son++;
        }
        low[u]=min (low[u],dfn[v]);
    }
    if(son>=2&&u==father)
    xis[u]=1;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])
		dfs(i,i);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(xis[i])
		ans++;
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		if(xis[i])
		cout<<i<<" ";
	}
} 
2022/5/11 16:51
加载中...