#117. 歐拉回路
有一天一位靈魂畫師畫了一張圖，現在要你找出歐拉回路，即在圖中找一個環使得每條邊都在環上出現恰好一次。
一共兩個子任務：
- 這張圖是無向圖。（50分）
輸入格式
第一行一個整數 t，表示子任務編号。t∈{1,2}，如果 t=1則表示處理無向圖的情況，如果 t=2 則表示處理有向圖的情況。
第二行兩個整數 n,m，表示圖的結點數和邊數。
接下來 m 行中，第 i 行兩個整數 vi,ui，表示第 ii 條邊（從 11 開始編号）。保證 1≤vi,ui≤n
圖中可能有重邊也可能有自環。
- 如果 t=1
- 則表示 vi 到 ui 有一條無向邊。
- 如果 t=2
- 則表示 vi 到 ui 有一條有向邊。
輸出格式
如果不可以一筆畫，輸出一行 “NO”。
否則，輸出一行 “YES”，接下來一行輸出一組方案。
如果 t=1，輸出 m個整數 p1,p2,…,pm。令 e=∣pi∣，那麼 e 表示經過的第 i 條邊的編号。如果 pi 為正數表示從 ve 走到 ue，否則表示從 ue 走到 ve。
如果 t=2，輸出 m 個整數 p1,p2,…,pm。其中 pi 表示經過的第 i條邊的編号。
樣例一
input
1 3 3 1 2 2 3 1 3output
YES 1 2 -3樣例二
2 5 6 2 3 2 5 3 4 1 2 4 2 5 1
YES 4 1 3 5 2 6限制與約定
1≤n≤10^5,0≤m≤2×10^5
時間限制：1s
空間限制：256MB
【分析】
這是歐拉回路的模闆題。
主要是這樣：
無向圖：所有點的度數都為偶數，一定有歐拉回路，從任意一個點開始都可以。
有向圖：所有點的入度=出度，一定有歐拉回路，從任意一個點開始都可以。
我們不斷走邊，邊沒打過标記的就走，經過一條邊就打标記，表示不能走這條邊了，然後回溯的時候把路徑記錄下來，反着輸出就可以。
走過的邊不僅要打标記（主要是無向圖的反向邊要标記一下），還要删除，不然即使不再走這條邊也會不斷詢問它而導緻TLE，
解決方法是改變邊目錄的first數組，表示前面通路過的邊都不用再繼續通路了。
void ffind(int x)
{
vis[x]=1;
for(int i=first[x];i;i=first[x]) if(t[i].p)
{
int y=t[i].y;
t[i].p=t[t[i].o].p=0;
first[x]=t[i].next;
ffind(y);
op[++op[0]]=t[i].id;
}
else first[x]=t[i].next;
}
核心代碼如上。
【GDXB當初告訴我這叫套圈算法？
【主要是回溯那裡還有删邊那裡要記得。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 #include<queue>
7 #include<stack>
8 using namespace std;
9 #define Maxm 200010
10 #define Maxn 100010
11
12 struct node
13 {
14 int x,y,c,next,o;
15 int id;
16 bool p;
17 }t[2*Maxm];
18 int first[Maxn],len;
19 int T;
20
21 void ins(int x,int y,int id)
22 {
23 t[++len].x=x;t[len].y=y;t[len].p=1;
24 t[len].id=id;t[len].next=first[x];first[x]=len;
25 if(T==1) t[len].o=len&1?len+1:len-1;
26 else t[len].o=len;
27 }
28
29 int rd[Maxn],cd[Maxn],op[Maxm];
30 bool nw=0,vis[Maxn];
31
32 void ffind(int x)
33 {
34 vis[x]=1;
35 for(int i=first[x];i;i=first[x]) if(t[i].p)
36 {
37 int y=t[i].y;
38 t[i].p=t[t[i].o].p=0;
39 first[x]=t[i].next;
40 ffind(y);
41 op[++op[0]]=t[i].id;
42 }
43 else first[x]=t[i].next;
44 }
45
46 int main()
47 {
48 scanf("%d",&T);
49 int n,m;
50 scanf("%d%d",&n,&m);
51 len=0;
52 memset(first,0,sizeof(first));
53 memset(rd,0,sizeof(rd));
54 memset(cd,0,sizeof(cd));
55 for(int i=1;i<=m;i++)
56 {
57 int x,y;
58 scanf("%d%d",&x,&y);
59 rd[y]++;cd[x]++;
60 ins(x,y,i);
61 if(T==1) ins(y,x,-i);
62 }
63 bool ok=1;
64 for(int i=1;i<=n;i++) if(T==1&&(rd[i]+cd[i])%2!=0) {ok=0;break;}
65 for(int i=1;i<=n;i++) if(T==2&&rd[i]!=cd[i]) {ok=0;break;}
66 op[0]=0;
67 if(!ok) printf("NO\n");
68 else
69 {
70 for(int i=1;i<=n;i++) vis[i]=0;
71 for(int i=1;i<=n;i++)
72 {
73 ffind(i);
74 if(op[0]!=0) break;
75 }
76 if(T==1&&op[0]!=len/2) printf("NO\n");
77 else if(T==2&&op[0]!=len) printf("NO\n");
78 else
79 {
80 printf("YES\n");
81 for(int i=op[0];i>=1;i--)
82 {
83 printf("%d ",op[i]);
84 }
85 printf("\n");
86 }
87
88 }
89 return 0;
90 } View Code