以n的剩余系为点，然后用同余定理建图
即以任意x为起点，它的临界点为y=[x(mod n) * 10(mod n)](mod n)
和z=(y+1) (mod n)
只需要找到一条由1至0的路径，然后输出路径就好了
代码如下：
#include<iostream>
#include<queue>
using namespace std;

void bfs();
void dfs(int);
void ins();
int n;
int pr[210];
bool V[210];
int A[210][2];//利用邻接表存储每个点的临接点

int main()
{
	while(cin>>n && n!=0)
	{
		if(n==1)
			cout<<n<<endl;
		else
		{
			ins();//建图
			bfs();
			cout<<endl;
		}
	}
	return 0;
}

void ins()
{
	for(int i=1;i<=n-1;i++)
	{
		int p=( (i%n)*(10%n) ) %n;//同余定理
		A[i][0]=p;//乘十
		A[i][1]=(p+1)%n;//乘十加一
	}
}

void bfs()//
{
	queue<int> Q;
	int i,j,k;
	for(i=0;i<=n;i++)
		pr[i]=i;
	memset(V,0,sizeof(V));
	Q.push(1);
	V[1]=true;
	while(V[0]==false)
	{
		int x=Q.front();
		Q.pop();
		for(i=0;i<=1;i++)
		{
			int y=A[x][i];
			if(!V[y])
			{
				pr[y]=x;
				Q.push(y);
				V[y]=1;
			}
		}
		
	}
	cout<<1;//1为起点
	dfs(0);
}

void dfs(int x)//递归查找路径
{
    if(x!=1)
    {	
        dfs(pr[x]);
        int c=A[pr[x]][0];
	if(c==x)
		printf("0");//乘十
	else
		printf("1");//乘十加一
     }
	return ;
}

• Re:建图然后bfs，23333 (1277) zhepeng123 2016-11-29 16:45:08