Problem Description

從前一個和諧的班級，所有人都是搞OI的。有 n 個是男生，有 0 個是女生。男生編號分別為 1,…,n。

現(xiàn)在老師想把他們分成若干個兩人小組寫動態(tài)仙人掌，一個人負責搬磚另一個人負責吐槽。每個人至多屬于一個小組。

有若干個這樣的條件：第 v?個男生和第 u 個男生愿意組成小組。

請問這個班級里最多產(chǎn)生多少個小組？

Input

第一行兩個正整數(shù)，n,m。保證 n≥2。

接下來 m 行，每行兩個整數(shù) v,u 表示第 v 個男生和第 u?個男生愿意組成小組。保證 1≤v,u≤n，保證 v≠u，保證同一個條件不會出現(xiàn)兩次。

Output

第一行一個整數(shù)，表示最多產(chǎn)生多少個小組。

接下來一行 n 個整數(shù)，描述一組最優(yōu)方案。第 v 個整數(shù)表示 v 號男生所在小組的另一個男生的編號。如果 v 號男生沒有小組請輸出 0。

Examples

Input

10 20
9 2
7 6
10 8
3 9
1 10
7 1
10 9
8 6
8 2
8 1
3 1
7 5
4 7
5 9
7 8
10 4
9 1
4 8
6 3
2 5

Output

5
9 5 6 10 2 3 8 7 1 4

Input

5 4
1 5
4 2
2 1
4 3

Output

2
2 1 4 3 0

思路：

題目本質是給出 n 個點 m 條邊的無向圖，要求一個最大匹配并輸出任意一種方案

對于一般圖的匹配，使用帶花樹算法即可，本題是一個帶花樹裸題

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1073741824; const int N = 3000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Edge {int to,next; } edge[N*N*2]; int head[N],tot; int n;//n個點 int father[N],pre[N];//father記錄一個點屬于哪個一個點為根的花 int Q[N*N*2],first,tail;//bfs隊列 int match[N];//匹配 bool odd[N],vis[N];//odd記錄一個點為奇點/偶點，1為奇，0為偶 int timeBlock;//LCA時間戳 int top[N],rinedge[N];void addEdge(int x,int y) {//添邊edge[tot].to=y;edge[tot].next=head[x];head[x]=tot++; } int Find(int x){//并查集尋找根節(jié)點if(father[x]!=x)return father[x]=Find(father[x]);return x; } int lca(int x, int y){//求解最近公共祖先timeBlock++;while(x){rinedge[x]=timeBlock;x=Find(top[x]);}x=y;while(rinedge[x]!=timeBlock)x=Find(top[x]);return x; } void blossom(int x, int y, int k) {//將奇環(huán)縮成一個點并將原來是奇點的點變?yōu)榕键c并加入隊列while(Find(x)!=Find(k)){pre[x]=y;y=match[x];odd[y]=false;Q[tail++]=y;father[Find(x)]=k;father[Find(y)]=k;x=pre[y];} } bool bfs(int s) {memset(top,0,sizeof(top));memset(pre,0,sizeof(pre));memset(odd,false,sizeof(odd));memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++)father[i]=i;vis[s]=true;first=tail=0;Q[tail++]=s;while(first!=tail){int now=Q[first++];for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(!vis[to]){top[to]=now;pre[to]=now;odd[to]=true;vis[to]=true;if(!match[to]){int j=to;while(j){int x=pre[j];int y=match[x];match[j]=x;match[x]=j;j=y;}return true;}vis[match[to]]=true;top[match[to]]=to;Q[tail++]=match[to];}else if(Find(now)!=Find(to) && odd[to]==false) {int k=lca(now,to);blossom(now,to,k);blossom(to,now,k);}}}return false; }int main() {memset(head,-1,sizeof(head));memset(match,0,sizeof(match));tot=0;int m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addEdge(x,y);addEdge(y,x);}int res=0;for(int i=1;i<=n;i++)if(!match[i])res+=bfs(i);printf("%d\n",res);for(int i=1;i<=n;i++)printf("%d ",match[i]);printf("\n");return 0; }

總結

以上是生活随笔為你收集整理的一般图最大匹配（UOJ-79）的全部內容，希望文章能夠幫你解決所遇到的問題。

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