【cf789D】Weird journey（歐拉路、計數）

cf788B/789D. Weird journey

題意

n個點m條邊無重邊有自環無向圖，問有多少種路徑可以經過m-2條邊兩次，其它兩條邊1次。邊集不同的路徑就是不同的。

題解

将所有非自環的邊變成兩份。然後去掉兩條邊，看有沒有歐拉路。

如果兩條邊都不是自環，那麼隻當他們相鄰時（共享一個點），剩下的圖有兩個奇數度的點。有歐拉路。是以第i個點作為共享的點，有\(C(cnt_i,2)\)種路徑。

如果其中一個是自環，那麼其他m-1條邊任意選一個都可以。有loop*（m-1）條，不過每個自環算了兩次。是以要減去C(loop,2)。

注意判斷一下圖是不是聯通的，不聯通答案是0。

代碼

const int N=1001000;
int f[N];
int n,m;
VI e[N];
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
ll loop;
ll ans;
bool o[N];
int main() {
	ios::sync_with_stdio(false);//！！！TLE
	cin>>n>>m;
	rep(i,1,n+1)f[i]=i;
	
	int u,v;
	rep(i,0,m){
		cin>>u>>v;
		o[u]=o[v]=1;
		if(u==v)++loop;
		int fu=find(u),fv=find(v);
		if(fu!=fv)f[fu]=fv;
		if(u!=v){e[u].pb(v);e[v].pb(u);}
	}
	rep(i,1,n+1)if(o[i]&&find(i)!=find(u))ans=-1;//o[i]：出現過的點。
	if(~ans){
		ans=loop*(m-1)-(loop-1)*loop/2;
		rep(i,1,n+1)ans+=(ll)(SZ(e[i])-1)*SZ(e[i])/2;
		cout<<ans<<endl;
	}
	else cout<<"0";
	return 0;
}
           

┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆　┆可┆有┆謙┆戮┆那┆　┆大┆始┆　┆然┆

┆薄┆一┆臨┆你┆的┆還┆沒┆　┆來┆　┆是┆來┆遜┆沒┆些┆　┆雁┆終┆　┆而┆

┆　┆暖┆　┆如┆地┆站┆有┆　┆也┆　┆我┆　┆的┆有┆精┆　┆也┆沒┆　┆你┆

┆　┆這┆　┆試┆方┆在┆逃┆　┆會┆　┆在┆　┆清┆來┆準┆　┆沒┆有┆　┆沒┆

┆　┆生┆　┆探┆　┆最┆避┆　┆在┆　┆這┆　┆晨┆　┆的┆　┆有┆來┆　┆有┆

┆　┆之┆　┆般┆　┆不┆　┆　┆這┆　┆裡┆　┆沒┆　┆殺┆　┆來┆　┆　┆來┆