关于厌氧
查看原帖
关于厌氧
530468
_determination_楼主2024/4/18 17:17

rt 这是我写的代码,为什么会厌氧?(并查集merge操作)

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
map<int,int>mp[3010];
vector<pair<int,int> >e[3010];
int dfn[3010],low[3010],tot,scc;
int u[4510],v[4510],id[3010];
stack<int>st;
void tarjan(int x,int f)
{
	dfn[x]=low[x]=++tot;
	st.push(x);
	int flag=0;
	for ( int i = 0 ; i < e[x].size() ; i++ )
	{
		int v=e[x][i].first,w=e[x][i].second;
		if(w==0)continue;
		if(v==f&&flag==0)
		{
			flag=1;
			continue;
		}
		if(!dfn[v])
		{
			tarjan(v,x);
			low[x]=min(low[x],low[v]);
		}else{
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(dfn[x]==low[x])
	{
		scc++;
		while(st.top()!=x)
		{
			id[st.top()]=scc;
			st.pop();
		}
		id[x]=scc;
		st.pop();
	}
}
unsigned long long hsh[3010];
const int base=19491001;
int ccid[3010];
struct DSU{
	int a[3010];
	void init()
	{
		for ( int i = 1 ; i <= 3000 ; i++ )
		{
			a[i]=i;
		}
	}
	int find(int x)
	{
		assert(x<=3000);
		assert(x>0);
		if(a[x]==x)return x;
		return a[x]=find(a[x]);
	}
	int merge(int u,int v)
	{
		a[find(u)]=find(v);
	}
}dsu;
signed main()
{
	int n,m;
	cin >> n >> m;
	dsu.init();
	for ( int i = 1 ; i <= m ; i++ )
	{
		cin >> u[i] >> v[i];
		dsu.merge(u[i],v[i]);
		mp[u[i]][v[i]]=e[u[i]].size();
		e[u[i]].push_back({v[i],1});
		mp[v[i]][u[i]]=e[v[i]].size();
		e[v[i]].push_back({u[i],1});
	}
	for ( int i = 1 ; i <= n ; i++ )
	{
		if(!dfn[i])tarjan(i,i);
	}
	for ( int i = 1 ; i <= n ; i++ )
	{
		ccid[i]=id[i];
	}
	for ( int i = 1 ; i <= m ; i++ )
	{
		e[u[i]][mp[u[i]][v[i]]].second=0;
		e[v[i]][mp[v[i]][u[i]]].second=0;
		tot=scc=0;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(id,0,sizeof(id));
		for ( int j = 1 ; j <= n ; j++ )
		{
			if(!dfn[j])tarjan(j,j);
		}
		for ( int j = 1 ; j <= n ; j++ )
		{
			hsh[j]=hsh[j]*base+id[j];
		}
		e[u[i]][mp[u[i]][v[i]]].second=1;
		e[v[i]][mp[v[i]][u[i]]].second=1;
	}
	int ans=0;
	for ( int i = 1 ; i <= n ; i++ )
	{
		for ( int j = i+1 ; j <= n ; j++ )
		{
			if(dsu.find(i)!=dsu.find(j))continue;
//			cout << i << " " << j << endl;
			if(ccid[i]!=ccid[j])
			{
				ans++;
				continue;
			}
//			cout << i << " " << j << endl;
			if(hsh[i]!=hsh[j])
			{
				ans+=2;
				continue;
			}
//			cout << i << " " << j << endl;
			ans+=3;
		}
	}
	cout << ans;
	return 0;
}
2024/4/18 17:17
加载中...