P3388 割点模版题
  • 板块题目总版
  • 楼主微分几何
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/10/26 17:13
  • 上次更新2023/11/5 09:49:33
查看原帖
P3388 割点模版题
120190
微分几何楼主2020/10/26 17:13

本蒟蒻只会本来就连通的图,但测试数据可能不连通,只有44分,求助大佬!!!

#include <bits/stdc++.h>
using namespace std;
const int SIZE=100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE];//,stack[SIZE];
bool cut[SIZE*2];
int n,m,tot,num,root;
void add(int x,int y)
{
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++num;
	int flag=0;
	for(int i=head[x];i;i=Next[i])
	{
		int y=ver[i];
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x])
			{
				flag++;
				if(x!=root||flag>1)	cut[x]=true;
			}
		}
		else	low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	cin>>n>>m;
	tot=1;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		if(x==y)	continue;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			root=i;
			tarjan(i);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(cut[i]==true)	ans++;
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
	{
		if(cut[i]==true)
		{
			cout<<i<<endl;
		}
	}
    return 0;
}
2020/10/26 17:13
加载中...