带花树

2019-04-13 11:28发布

站内文章 / 模拟电子
16635 0 1477
#include using namespace std; int n, m, tl, hed[505], mp[505], cnt, f[505], jb[505], pre[505]; int inx, vis[505]; struct node { int v, nxt; }e[500005]; void add(int u, int v) { e[++tl].v = v; e[tl].nxt = hed[u]; hed[u] = tl; } int fth(int x) { return f[x] == x ? x : f[x] = fth(f[x]); } queueque; int lca(int x, int y) { ++inx; for(;;swap(x, y)) { if(!x) continue; x = fth(x); if(vis[x] == inx) return x; vis[x] = inx; x = pre[mp[x]]; } } void unit(int u, int v, int t) { int z; while(fth(u) != t) { pre[u] = v; z = mp[u]; if(jb[z] == 2) { jb[z] = 1; que.push(z); } if(fth(u) == u) f[u] = t; if(fth(z) == z) f[z] = t; v = z; u = pre[v]; } } bool find(int s) { int i, j; for(i = 1; i <= n; ++i) { f[i] = i; jb[i] = -1; } while(!que.empty()) que.pop(); que.push(s); jb[s] = 1; int u, v, x1, x2, t, las, now; while(!que.empty()) { u = que.front(); que.pop(); for(i = hed[u]; ~i; i = e[i].nxt) { v = e[i].v; if(jb[v] < 0) { jb[v] = 2; pre[v] = u; if(!mp[v]) { now = v; for(; now; now = las) { las = mp[t = pre[now]]; mp[now] = t; mp[t] = now; } return 1; } else { jb[mp[v]] = 1; que.push(mp[v]); } } else if(jb[v] == 1 && fth(u) != fth(v)){ t = lca(u, v); unit(u, v, t); unit(v, u, t); } } } return 0; } int main() { cin >> n >> m; memset(hed, -1, sizeof(hed)); int i, u, v, j; for(i = 1; i <= m; ++i) { cin >> u >> v; add(u, v); add(v, u); } for(i = 1; i <= n; ++i) { if(mp[i]) continue; if(find(i)) ++cnt; } cout << cnt << endl; for(i = 1; i <= n; ++i) cout << mp[i] << " "; return 0; }  

热门文章