| 11 | while (s) { |
| 12 | int v = S[--s]; |
| 13 | iter(wt,adj[v]) { |
| 14 | int w = *wt; |
| 15 | if (emarked[v][w]) continue; |
| 16 | if (root[w] == -1) { |
| 17 | int x = S[s++] = m[w]; |
| 18 | par[w]=v, root[w]=root[v], height[w]=height[v]+1; |
| 19 | par[x]=w, root[x]=root[w], height[x]=height[w]+1; |
| 20 | } else if (height[w] % 2 == 0) { |
| 21 | if (root[v] != root[w]) { |
| 22 | while (v != -1) q.push_back(v), v = par[v]; |
| 23 | reverse(q.begin(), q.end()); |
| 24 | while (w != -1) q.push_back(w), w = par[w]; |
| 25 | return q; |
| 26 | } else { |
| 27 | int c = v; |
| 28 | while (c != -1) a.push_back(c), c = par[c]; |
| 29 | c = w; |
| 30 | while (c != -1) b.push_back(c), c = par[c]; |
| 31 | while (!a.empty()&&!b.empty()&&a.back()==b.back()) |
| 32 | c = a.back(), a.pop_back(), b.pop_back(); |
| 33 | memset(marked,0,sizeof(marked)); |
| 34 | fill(par.begin(), par.end(), 0); |
| 35 | iter(it,a) par[*it] = 1; iter(it,b) par[*it] = 1; |
| 36 | par[c] = s = 1; |
| 37 | rep(i,0,n) root[par[i] = par[i] ? 0 : s++] = i; |
| 38 | vector<vi> adj2(s); |
| 39 | rep(i,0,n) iter(it,adj[i]) { |
| 40 | if (par[*it] == 0) continue; |
| 41 | if (par[i] == 0) { |
| 42 | if (!marked[par[*it]]) { |
| 43 | adj2[par[i]].push_back(par[*it]); |
| 44 | adj2[par[*it]].push_back(par[i]); |
| 45 | marked[par[*it]] = true; } |
| 46 | } else adj2[par[i]].push_back(par[*it]); } |
| 47 | vi m2(s, -1); |
| 48 | if (m[c] != -1) m2[m2[par[m[c]]] = 0] = par[m[c]]; |
| 49 | rep(i,0,n) if(par[i]!=0&&m[i]!=-1&&par[m[i]]!=0) |
| 50 | m2[par[i]] = par[m[i]]; |
| 51 | vi p = find_augmenting_path(adj2, m2); |
| 52 | int t = 0; |
| 53 | while (t < size(p) && p[t]) t++; |
| 54 | if (t == size(p)) { |
| 55 | rep(i,0,size(p)) p[i] = root[p[i]]; |
| 56 | return p; } |
| 57 | if (!p[0] || (m[c] != -1 && p[t+1] != par[m[c]])) |
| 58 | reverse(p.begin(), p.end()), t=(int)size(p)-t-1; |
| 59 | rep(i,0,t) q.push_back(root[p[i]]); |
| 60 | iter(it,adj[root[p[t-1]]]) { |
| 61 | if (par[*it] != (s = 0)) continue; |
| 62 | a.push_back(c), reverse(a.begin(), a.end()); |
| 63 | iter(jt,b) a.push_back(*jt); |
| 64 | while (a[s] != *it) s++; |
| 65 | if((height[*it]&1)^(s<(int)size(a)-(int)size(b))) |
| 66 | reverse(a.begin(),a.end()), s=(int)size(a)-s-1; |
| 67 | while(a[s]!=c)q.push_back(a[s]),s=(s+1)%size(a); |
| 68 | q.push_back(c); |
| 69 | rep(i,t+1,size(p)) q.push_back(root[p[i]]); |
| 70 | return q; } } } |
no test coverage detected