边双连通分量求调
  • 板块学术版
  • 楼主FormulaOne
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/9 09:02
  • 上次更新2023/11/3 05:03:41
查看原帖
边双连通分量求调
180406
FormulaOne楼主2023/8/9 09:02

rt,模板调不过去,悬关

#include <bits/stdc++.h>
#define int long long

using namespace std;

vector<int> G[1000001];
vector<int> d[1000001];
int n,m,a[2000001],ans,dfn,low[2000001],num[2000001],pd[2000001],st[2000001],tp,c[2000001],stpd[2000001];

void dfs( int u ,int fa)
{
	dfn ++;
	low[u] = num[u] = dfn;
	pd[u] = 1;
	st[++ tp] = u;
	stpd[u] = 1;
	for( int i = 0 ; i < G[u].size() ; i ++ )	
	{
		int v = G[u][i];
		if( !pd[v] && v != fa ) 
		{
			dfs( v , u );
			low[u] = min( low[u] , low[v] );
		}
		else low[u] = min( low[u] , num[v] );
	}
	if( low[u] == num[u] )
	{
		ans ++;
		while( st[tp] != u )
			d[ans].push_back( st[tp] ),stpd[st[tp]] = 0,tp --;
		d[ans].push_back( u ),tp --;
		stpd[u] = 0;
	}
}
signed main()
{
	int u,v;
	cin >> n >> m;
	for( int i = 1 ; i <= m ; i ++ )
	{
		cin >> u >> v;
		c[u] ++;
		c[v] ++;
		G[u].push_back( v );
		G[v].push_back( u );
	}
	for( int i = 1 ; i <= n ; i ++ )
		if( num[i] == 0 )
			dfs( i , -1 );
	cout << ans << endl;
	for( int i = 1 ; i <= ans ; i ++ )
	{
		cout << d[i].size() << ' ';
		for( int j = 0 ; j < d[i].size() ; j ++ )	
			cout << d[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

2023/8/9 09:02
加载中...