T235題目：輸入集合A和B，輸出A到B上的所有單射函數(shù)。

問題描述

給定非空數(shù)字集合A和B，求出集合A到集合B上的所有單射函數(shù)。

輸入格式

第一行輸入m和n（空格間隔），分別為集合A和集合B中的元素個(gè)數(shù)；

第二行輸入非空數(shù)字集合A，每個(gè)元素之間用空格間隔；

第三行輸入非空數(shù)字集合B，每個(gè)元素之間用空格間隔；

輸出格式

輸出每一行為集合A到集合B的一個(gè)構(gòu)成單射函數(shù)的二元關(guān)系，按二元關(guān)系的基數(shù)大小從小到大輸出所有二元關(guān)系，相同基數(shù)的二元關(guān)系按序偶中元素的字典序排列。

樣例輸入

2 2

1 2

3 4

樣例輸出

{<1,3>,<2,4>}

{<1,4>,<2,3>}

在T234基礎(chǔ)上，保證加入q集合中元素不重復(fù)即可，前者鏈接見下：

【xdoj-離散線上練習(xí)H】T234（C++）-CSDN博客

#include<bits/stdc++.h>
using namespace std;int main()
{//預(yù)處理：利用優(yōu)先隊(duì)列將集合中元素從小到大放進(jìn)數(shù)組A，B中int m, n, cur;cin>>m>>n;priority_queue<int>pq;	vector<int>A(m);vector<int>B(n);for(int i=0; i<m; i++) {cin>>cur; pq.push(cur);}for(int i=1; i<=m; i++) {A[m-i] = pq.top(); pq.pop();		}for(int i=0; i<n; i++) {cin>>cur; pq.push(cur);}for(int i=1; i<=n; i++) {B[n-i] = pq.top(); pq.pop();		}//觀察輸出樣例：每行輸出均有A中全部元素，B對(duì)應(yīng)元素每行只有一處變化vector<int>q(m);//q[i]攜帶了當(dāng)前映射關(guān)系中A[i]對(duì)應(yīng)的集合B中元素//為什么用遞歸：因?yàn)锳中元素?cái)?shù)量不確定，事實(shí)上，如果用for循環(huán)嵌套，那么for循環(huán)的數(shù)量為 m，這是不能在確定的代碼中實(shí)現(xiàn)的auto dfs = [&](auto& dfs, int cnt) -> void{if(cnt == m)//遞歸終止條件{cout<<"{";for(int i=0; i<m; i++){cout<<"<"<<A[i]<<","<<q[i]<<">";				if(i == m-1) cout<<"}"<<endl;else cout<<",";}return;			}else{//繼續(xù)遞歸for(int i=0; i<n; i++){//保證q中的元素不重復(fù)int k=0;for( ; k<cnt; k++){if(q[k] == B[i]) break;}	if(k == cnt)				{q[cnt] = B[i];dfs(dfs, cnt+1);}			}			return;}};dfs(dfs, 0);return 0;	
}

T236題目：輸入集合A和B，輸出A到B上的所有滿射函數(shù)。

只需將dfs函數(shù)替換成如下形式

auto dfs = [&](auto& dfs, int cnt) -> void{if(cnt == m)//遞歸終止條件{set<int>st;for(int i=0; i<m; i++){st.insert(q[i]);}if(st.size() == n){cout<<"{";for(int i=0; i<m; i++){cout<<"<"<<A[i]<<","<<q[i]<<">";				if(i == m-1) cout<<"}"<<endl;else cout<<",";}}return;			}else{//繼續(xù)遞歸for(int i=0; i<n; i++){q[cnt] = B[i];dfs(dfs, cnt+1);						}			return;}};

T237題目：輸入集合A和B，輸出A到B上的所有雙射函數(shù)。

將dfs換成這個(gè)就成

auto dfs = [&](auto& dfs, int cnt) -> void{if(cnt == m)//遞歸終止條件{set<int>st;for(int i=0; i<m; i++){st.insert(q[i]);}if(st.size() == n){cout<<"{";for(int i=0; i<m; i++){cout<<"<"<<A[i]<<","<<q[i]<<">";				if(i == m-1) cout<<"}"<<endl;else cout<<",";}}return;			}else{//繼續(xù)遞歸for(int i=0; i<n; i++){//保證q中的元素不重復(fù)int k=0;for( ; k<cnt; k++){if(q[k] == B[i]) break;}	if(k == cnt)				{q[cnt] = B[i];dfs(dfs, cnt+1);}							}			return;}};