菜鸡求助,调自闭了
查看原帖
菜鸡求助,调自闭了
220426
血色黄昏楼主2020/8/27 19:43

今天闲着没事打了一发割点代码,没过样例后对着zty神仙的题解看了几遍,改了后差不多主体部分是一样的除了变量,但还是没过样例,来学术版请教一下神仙们/kel

#include<bits/stdc++.h>
using namespace std;
int dfn[100010], low[100010], pa[100010], n, m, cnt = 0, tot = 0;
bool vis[100010];
vector<int>l[100010];
set<int>ans;
void tarjan(int u)
{
	vis[u] = false;
	low[u] = dfn[u] = ++ cnt;
	int child = 0;
	for(int i = 0;i < l[u].size();i ++)
	{
		int v = l[u][i];
		if(vis[v])
		{
			child ++;
			pa[v] = u;
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if ((low[v] >= dfn[u] and pa[u] != u))
			{
				ans.insert(u);
				tot ++;
			}
		}
		else if(pa[u] != v)low[u] = min(low[u], dfn[v]);	
	}
	if(pa[u] == u and child >= 2)
	{
		ans.insert(u);
		tot ++;
	}
}
int main()
{
	memset(vis, true, sizeof(vis));
	cin>>n>>m;
	for(int i = 1;i <= m;i ++)
	{
		int x, y;
		cin>>x>>y;
		l[x].push_back(y);
		l[y].push_back(x);
	}
	set<int>::iterator it;
	for(int i = 1;i <= n;i ++)
	{
		if(!vis[i])
		{
			pa[i] = i;
			cnt = 0;
			tarjan(i);
		}
	}
    cout<<tot<<endl;
    for(it=ans.begin();it!=ans.end ();it++)
    {
        cout<<*it<<' ';
    }
	return 0;
}

感觉马蜂还行就不加注释了吧

2020/8/27 19:43
加载中...