[福建集訓2011][LOJ10111]相框

這題主要還是分類討論歐拉回路

首先對于導線一端沒有東西的新建一個節點 由于原圖不一定連通所以需要用到并查集判斷有多少個連通塊 將一條導線連接的兩個焊點連接

然后先對于只有一個連通塊考慮

1.如果一個焊點是孤立點 它對于導線無影響跳過

2.如果一個焊點度數大于2 它必須被燒熔

3.對于每兩對奇點 它們必須相連 這樣才滿足歐拉回路

對于一個連通塊處理后考慮多個連通塊，必須把他們組合在一起

1.同樣忽略孤立點

2.如果原圖是一個環

需要找到一個點將其燒熔,才能繼續組合

但其中若有焊點度數大于2,那么它本身已經被燒熔了所以可以略去此步

最后每個連通塊向外和另一連通塊連接一根導線就組裝好了

3.原圖有鏈 這種情況下只要將一對奇點向外連就好了 當然對于程序來說就是無需考慮有鏈的連通塊連接的答案，以為這之前單個處理已經統計過了

#include<bits/stdc++.h>
using namespace std;
const int maxn=101005;
int tot,ans,n,m,a,b,cnt;
int d[maxn],flag1[maxn],flag2[maxn],fa[maxn];
int read()
{int ch=0,x=0;while(ch=getchar(),ch<'0'||ch>'9');while(x=x*10+ch-48,ch=getchar(),ch>='0'&&ch<='9');return x;
}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void conn(int x,int y)
{int fxx=getfa(x),fyy=getfa(y);if(fxx!=fyy)fa[fxx]=fyy;
}
int main()
{n=read();m=read();for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){a=read();b=read();if(!a) a=++n,fa[a]=a;if(!b) b=++n,fa[b]=b;conn(a,b);d[a]++;d[b]++;}for(int i=1;i<=n;i++){if(!d[i])continue;if(d[i]&1){cnt++;flag1[getfa(i)]=1;}if(d[i]>2){ans++;flag2[getfa(i)]=1;}}for(int i=1;i<=n;i++)if(getfa(i)==i&&d[i])tot++;if(tot>1){for(int i=1;i<=n;i++)if(getfa(i)==i&&d[i]&&!flag1[i]){ans++;if(!flag2[i])ans++;}}ans+=cnt/2;printf("%d",ans);return 0;
}