1to1_mapping_algorihms.cpp

上海交通大学研究生算法分析课的作业.实现了<<算法引论-一种创造性方法>>(Udi Manber 黄林鹏 电子工业出版社)第五章中的大部分算法

#include <iostream.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <stdlib.h> 

#ifdef _WIN32 
using namespace std; 
#endif 

using namespace std ;

typedef queue<int>  INTQUEUE;

void main()
{
	printf("寻找一对一映射算法\n");
	printf("\n作者:茹炳晟(学号:1060379162)\n");
	printf("\n说明：本算法解决一对一函数问题：f:A->A,找最大S属于A,使得f:S->S是一对一函数\n");
	
	INTQUEUE q;
	int n;                 //节点的个数
	int f[100];            //保存映射关系的数组
	int count[100];        //记数器数组
	printf("\n请输入节点的个数(n):");
	scanf("%i",&n);
    for(int i=1;i<=n;i++)
	{
		printf("请输入与第%i个节点关联的节点编号:",i);
		scanf("%i",&f[i]);
	}
	for(i=1;i<=n;i++)
	{
		count[i]=0;
	}
	for(i=1;i<=n;i++)
	{
		count[f[i]]++;
	}                     //至此初始化部分完成
	for(i=1;i<=n;i++)
	{
		if(count[i]==0)
			q.push(i);      
	}

	printf("\n所有的节点列表:  ");
	for(i=1;i<=n;i++)
	{
		printf("%i  ",i);
	}
    printf("\n");

	while(!q.empty())      
	{
        i=q.front();
	    q.pop();            
		cout<<"从以上节点列表中删除节点："<<i<<endl;      
		count[f[i]]--;
		if(count[f[i]]==0)
			q.push(f[i]);   
	}
	cout<<"删除以上的节点后，剩下的节点集合就构成了最大的一对一映射集合"<<endl;

	system("PAUSE"); 

}