1527：【例 1】歐拉回路

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 262144 KB

【題目描述】

原題來自：UOJ #117

有一天一位靈魂畫師畫了一張圖，現(xiàn)在要你找出歐拉回路，即在圖中找一個(gè)環(huán)使得每條邊都在環(huán)上出現(xiàn)恰好一次。

一共兩個(gè)子任務(wù)：

這張圖是無向圖。（50 分）

這張圖是有向圖。（50 分）

【輸入】

第一行一個(gè)整數(shù)?t，表示子任務(wù)編號(hào)。t∈{1,2}，如果?t=1?則表示處理無向圖的情況，如果?t=2?則表示處理有向圖的情況。

第二行兩個(gè)整數(shù)?n,m，表示圖的結(jié)點(diǎn)數(shù)和邊數(shù)。

接下來?m?行中，第?i?行兩個(gè)整數(shù)?vi,ui?，表示第?i?條邊（從?1?開始編號(hào)）。保證?1≤vi,ui≤n。

如果?t=1?則表示?vi?到?ui?有一條無向邊。

如果?t=2?則表示?vi?到?ui?有一條有向邊。

圖中可能有重邊也可能有自環(huán)。

【輸出】

如果不可以一筆畫，輸出一行?NO。

否則，輸出一行?YES，接下來一行輸出一組方案。

如果?t=1，輸出?m?個(gè)整數(shù)?p1,p2,…,pm?。令?e=|pi|，那么?e?表示經(jīng)過的第?i?條邊的編號(hào)。如果?pi為正數(shù)表示從?ve?走到?ue?，否則表示從?ue?走到?ve?。

如果?t=2，輸出?m?個(gè)整數(shù)?p1,p2,…,pm?。其中?pi?表示經(jīng)過的第?i?條邊的編號(hào)。

【輸入樣例】

1 3 3 1 2 2 3 1 3

【輸出樣例】

YES 1 2 -3

【提示】

樣例輸入 2

2 5 6 2 3 2 5 3 4 1 2 4 2 5 1

樣例輸出 2

YES 4 1 3 5 2 6

數(shù)據(jù)范圍與提示：

1≤n≤10^5,0≤m≤2×10^5

?

?

--------------------------放了一大坨概念在下面--------------------------

歐拉回路和歐拉路徑的幾個(gè)概念:

歐拉環(huán)：圖中經(jīng)過每條邊一次且僅一次的環(huán)；

歐拉路徑：圖中經(jīng)過每條邊一次且僅一次的路徑；
歐拉圖：有至少一個(gè)歐拉環(huán)的圖；
半歐拉圖：沒有歐拉環(huán)，但有至少一條歐拉路徑的圖。

【無向圖】
一個(gè)無向圖是歐拉圖當(dāng)且僅當(dāng)該圖是連通的（注意，不考慮圖中度為0的點(diǎn)，因?yàn)樗鼈兊拇嬖趯?duì)于圖中是否存在歐拉環(huán)、歐拉路徑?jīng)]有影響）且所有點(diǎn)的度數(shù)都是偶數(shù)；一個(gè)無向圖是半歐拉圖當(dāng)且僅當(dāng)該圖是連通的且有且只有2個(gè)點(diǎn)的度數(shù)是奇數(shù)（此時(shí)這兩個(gè)點(diǎn)只能作為歐拉路徑的起點(diǎn)和終點(diǎn)）；

證明：因?yàn)槿我庖粋€(gè)點(diǎn)，歐拉環(huán)（或歐拉路徑）從它這里進(jìn)去多少次就要出來多少次，故(進(jìn)去的次數(shù)+出來的次數(shù))為偶數(shù)，又因?yàn)?進(jìn)去的次數(shù)+出來的次數(shù))=該點(diǎn)的度數(shù)（根據(jù)定義），所以該點(diǎn)的度數(shù)為偶數(shù)。

【有向圖】
一個(gè)有向圖是歐拉圖當(dāng)且僅當(dāng)該圖的基圖（將所有有向邊變?yōu)闊o向邊后形成的無向圖，這里同樣不考慮度數(shù)為0的點(diǎn)）是連通的且所有點(diǎn)的入度等于出度；一個(gè)有向圖是半歐拉圖當(dāng)且僅當(dāng)該圖的基圖是連通的且有且只有一個(gè)點(diǎn)的入度比出度少1（作為歐拉路徑的起點(diǎn)），有且只有一個(gè)點(diǎn)的入度比出度多1（作為終點(diǎn)），其余點(diǎn)的入度等于出度。

證明：與無向圖證明類似，一個(gè)點(diǎn)進(jìn)去多少次就要出來多少次。

?

模板嘛。。。

?

1 /* 2 不懂為什么dfs里的i加個(gè)&可以快這么多 3 */ 4 #pragma comment(linker, "/STACK:102400000,102400000") 5 #include <bits/stdc++.h> 6 using namespace std; 7 const int N=100005,M=500005; 8 inline int read() 9 { 10 int s=0,f=0; 11 char ch=' '; 12 while(!isdigit(ch)) 13 { 14 f|=(ch=='-'); 15 ch=getchar(); 16 } 17 while(isdigit(ch)) 18 { 19 s=(s<<3)+(s<<1)+(ch^48); 20 ch=getchar(); 21 } 22 return (f)?(-s):(s); 23 } 24 #define R(x) x=read() 25 inline void write(int x) 26 { 27 if(x<0) 28 { 29 putchar('-'); 30 x=-x; 31 } 32 if(x<10) 33 { 34 putchar(x+'0'); 35 return; 36 } 37 write(x/10); 38 putchar((x%10)+'0'); 39 return; 40 } 41 inline void writeln(int x) 42 { 43 write(x); 44 putchar('\n'); 45 return; 46 } 47 #define W(x) write(x),putchar(' ') 48 #define Wl(x) writeln(x) 49 int n,m,T; 50 int Indeg[N],Outdeg[N],Deg[N]; 51 namespace Oulahuilu 52 { 53 int tot=0,Next[M],to[M],head[N]; 54 bool Arr[M]; 55 inline void add(int x,int y) 56 { 57 Next[++tot]=head[x]; 58 to[tot]=y; 59 head[x]=tot; 60 return; 61 } 62 int Huilu[M],Huilu_cnt=0; 63 inline void Run(int x) 64 { 65 for(int &i=head[x];i;i=Next[i]) if(!Arr[i]) 66 { 67 int oo=i; 68 Arr[i]=1; 69 if(T==1) 70 { 71 (i&1)?(Arr[i+1]=1):(Arr[i-1]=1); 72 } 73 Run(to[i]); 74 Huilu[++Huilu_cnt]=oo; 75 } 76 return; 77 } 78 inline void Output() 79 { 80 int i; 81 for(i=Huilu_cnt;i>=1;i--) 82 { 83 if(T==1) 84 { 85 W(((Huilu[i]&1)?1:-1)*((Huilu[i]+1)/2)); 86 } 87 else 88 { 89 W(Huilu[i]); 90 } 91 } 92 return; 93 } 94 } 95 int main() 96 { 97 // freopen("tour14.in","r",stdin); 98 // freopen("my.out","w",stdout); 99 int i; 100 R(T); 101 R(n); 102 R(m); 103 if(T==1) 104 { 105 106 for(i=1;i<=m;i++) 107 { 108 int x,y; 109 R(x); 110 R(y); 111 Deg[x]++; 112 Deg[y]++; 113 Oulahuilu::add(x,y); 114 Oulahuilu::add(y,x); 115 } 116 for(i=1;i<=n;i++) if(Deg[i]&1) 117 { 118 return 0*puts("NO"); 119 } 120 for(i=1;i<=n;i++) if(Oulahuilu::head[i]) 121 { 122 Oulahuilu::Run(i); 123 break; 124 } 125 if(Oulahuilu::Huilu_cnt!=m) 126 { 127 puts("NO"); 128 } 129 else 130 { 131 puts("YES"); 132 Oulahuilu::Output(); 133 } 134 } 135 else 136 { 137 for(i=1;i<=m;i++) 138 { 139 int x,y; 140 R(x); 141 R(y); 142 Outdeg[x]++; 143 Indeg[y]++; 144 Oulahuilu::add(x,y); 145 } 146 for(i=1;i<=n;i++) if(Indeg[i]!=Outdeg[i]) 147 { 148 return 0*puts("NO"); 149 } 150 for(i=1;i<=n;i++) if(Oulahuilu::head[i]) 151 { 152 Oulahuilu::Run(i); 153 break; 154 } 155 if(Oulahuilu::Huilu_cnt!=m) 156 { 157 puts("NO"); 158 } 159 else 160 { 161 puts("YES"); 162 Oulahuilu::Output(); 163 } 164 } 165 return 0; 166 } 167 /* 168 input 169 1 170 3 3 171 1 2 172 2 3 173 1 3 174 output 175 YES 176 1 2 -3 177 178 input 179 2 180 5 6 181 2 3 182 2 5 183 3 4 184 1 2 185 4 2 186 5 1 187 output 188 YES 189 4 1 3 5 2 6 190 191 input 192 2 193 100000 3 194 41700 41700 195 15415 31090 196 31090 15415 197 output 198 NO 199 */ View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/gaojunonly1/p/10348777.html

總結(jié)

以上是生活随笔為你收集整理的一本通1527欧拉回路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。