【題解】相框 - tw511教學網

問題 B: 相框
時間限制: 1 Sec 記憶體限制: 256 MB
題目描述
【問題描述】
P大的基礎電路實驗課是一個無聊至極的課。每次實驗，T君總是提前完成，管理員卻不讓T君離開，T君只能幹坐在那兒無所事事。
先說說這個實驗課，無非就是把幾根導線和某些元器件（電阻、電容、電感等）用焊錫焊接起來。
為了打發時間，T君每次實驗做完後都在焊接一些詭異的東西，這就是他的傑作：
T君不滿足於焊接奇形怪狀的作品，強烈的破壞慾驅使他拆掉這個作品，然後將之焊接成規整的形狀。這會兒，T君正要把這個怪物改造成一個環形，當作自己的相框，步驟如下：
T君約定了兩種操作：

燒熔一個焊點：使得連線在焊點上的某些導線相分離或保持相連（可以理解為：把焊點上的導線劃分為若干個類，相同類中的導線相連，不同類之間的導線相離）

將兩根導線的自由端（即未與任何導線相連的一端）焊接起來。

例如上面的步驟中，先將A點燒熔，使得導線1與導線2、4點分離；再將D點燒熔，使得4、5與3、7相離；再燒熔E，使7與6、8相離；最後將1、7相連。

T君想用最少的操作來將原有的作品改造成為相框（要用上所有的導線）。

【輸入檔案】
輸入檔案的第一行共有兩個整數n和m：分別表示原有的作品的焊點和導線的數量 (0 ≤ n ≤ 1 000, 2 ≤ m ≤ 50 000)。焊點的標號為1~n。

接下來的m行每行共有兩個整數：導線兩端所連線的兩個焊點的標號，若不與任何焊點相連，則將這一端標號為0。

原有的作品可能不是連通的。

某些焊點可能只有一根導線與之相連，在該導線的這一端與其他導線相連之前，這些焊點不允許被燒熔。

某些焊點甚至沒有任何導線與之相連，由於T君只關心導線，因此這些焊點可以不被考慮。

【輸出檔案】
輸出檔案只包含一個整數：表示T君需要將原有的作品改造成相框的最少步數。

【輸入樣例1】
6 8

1 2

1 3

3 4

1 4

4 6

5 6

4 5

1 5

【輸出樣例1】
4

【輸入樣例2】
0 2

0 0

【輸出樣例2】
2

【輸入樣例3】
3 3

0 1

0 0

2 2

【輸出樣例3】
4

【資料規模和約定】
30%的資料中n≤10；

100%的資料中n≤1000。

歐拉回路：

寫這篇題解之前我也不會的預備知識：
　　　　尤拉通路：從圖中一個點出發不重複地遍歷所有邊的路徑（可以停在另一個點）
　　　　歐拉回路：從圖中一個點出發不重複地遍歷所有邊的迴路（必須回到出發點）
　　　　尤拉圖:存在歐拉回路的圖。判斷無向圖為尤拉圖的充要條件是所有點的度數均為偶數。
　　　　半尤拉圖:存在尤拉通路的圖。判斷無向圖為尤拉圖的充要條件是所有點的度數均為偶數或只有兩個點的度數為奇數
　　　　一個圖中如果存在度數為奇數的點，那麼這樣的點一定有偶數個。

解析：

圖片自己去找。。。
因為最終情況要滿足所有點的度數都是2（度數一開始就是0的點直接扔掉）所以我們要對所有度數大於2的點都要被熔燒。奇數的熔成一堆2度數的點+一個單個的點。
那麼現在有兩種情況

只有一個聯通塊，也就是所有邊都連在一起。只要把所有度數大於2的點熔成度數<=2的點，再把所有單個的點（熔出來的+本來就有的）兩兩配對組一起即可。自己試一下就是這樣的，所以沒必要管誰和誰連了。
有多個聯通塊，就要把所有的聯通塊都變成環，然後把所有環再熔成一條鏈，再把所有鏈連起來。。。對於過程中出現1度數點的聯通塊只要少熔和一對就好了。如果沒有1度數點，但在過程中有把偶數點熔成2度數點的過程，就可以把一對2度數點熔成兩個單個的就好了。

聯通塊用並查集就行了。
但是那堆0很令人尷尬.。。每個0新建一個點就好了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50000*2+1001;

//sum:單鏈個數
//ans:熔點的次數
//flag[]:是否有熔點操作
//cut[]:是否有奇數點
//in[]:度數
//tot:點數

void read(int &x) {
	x=0;int f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
}



int n,m,in[N],fa[N],tot=n,con,sum,ans,cut[N],flag[N];
//ans是熔點的個數，sum是單鏈的個數（單鏈兩端度數一定為奇，熔點不改變其它點的度）
//這裡就要求我們熔點時不產生自環（是否特判？）
//多個聯通塊則分別單獨操作再累加，只需特判是否本來是環（+1） 


int find(int x) {
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}


int main() {
	read(n),read(m);
	tot=n;
	for(int i=1;i<=2*m+n;i++) fa[i]=i;
	for(int i=1,x,y;i<=m;i++) {
		read(x),read(y);
		if(x==0) x=++tot;
		if(y==0) y=++tot;
		int u=find(x),v=find(y);
		if(u!=v) fa[u]=v;
		in[x]++,in[y]++;
	}
	for(int i=1;i<=tot;i++)
	    if(fa[i]==i&&in[i]) con++;
	if(con==1) {
		//printf("yes");
		for(int i=1;i<=tot;i++) {
			if(!in[i]) continue;
			if(in[i]&1) sum++;
			if(in[i]>2) ans++;
		}
	}
	else {
		for(int i=1;i<=tot;i++) {
			if(!in[i]) continue;
			if(in[i]&1) sum++,cut[find(i)]=1;
			if(in[i]>2) ans++,flag[find(i)]=1;
		}
		for(int i=1;i<=tot;i++) {
			if(in[i]&&fa[i]==i&&!cut[i]) {
				ans++;
				if(!flag[i]) ans++;
			}
		}
	}
	printf("%d",ans+sum/2);
}