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;
}