#include<iostream>
#include<string>
#include<map>
using namespace std;
int data[50][50];	//记录两个数字之间是否有边
int visited[50];	//深搜时标记是否被遍历
int out[50];		//每个数字出度的个数
int in[50];			//每个数字入度的个数
int n=1;			//数字的个数
void dfs(int now)
{	//从now结点开始进行深搜
	visited[now]=1;
	for(int i=1; i<=n; ++i)
	{
		if(data[now][i] && !visited[i])
		{	//有边，未遍历
			dfs(i);
		}
	}
}
bool connected(int now)
{	//是否输入的点是单向联通
	memset(visited, 0, sizeof(visited));
	dfs(now);
	for(int i=1; i<=n; ++i)
	{
		if(!visited[i] && (in[i]>0||out[i]>0))
		{	//必须保证该点确实存在
			return false;
		}
	}
	return true;
}

int main()
{
//	freopen("in.txt", "r", stdin);
	string str1, str2;	//记录输入的字符串
	map<string, int> m;
	while(cin>>str1>>str2)
	{
		if(m[str1]==0)
		{
			m[str1]=n;
			n++;
		}
		if(m[str2]==0)
		{
			m[str2]=n;
			n++;
		}
		data[m[str1]][m[str2]]++;
		out[m[str1]]++;
		in[m[str2]]++;
	}
	int in_num=0;		//入度大于出度的元素的个数
	int out_num=0;		//出度大于入度的元素的个数
	int out_loc=m[str1];//记录出度大于入度的结点,它的初值不能随意取,必须保证该点存在
	bool flag=0;		//标记能否成功
	for(int i=1; i<=n; ++i)
	{
		if(out[i]-in[i]<-1||out[i]-in[i]>1)
		{
			flag=1;		//标记失败
			break;
		}
		if(out[i]>in[i])
		{
			out_num++;
			out_loc=i;	//记录遍历的初值
		}
		if(out[i]<in[i])
		{
			in_num++;
		}
	}
	if(flag||out_num>1||in_num>1||out_num!=in_num||!connected(out_loc))
	{
		cout<<"Impossible"<<endl;
	}else{
		cout<<"Possible"<<endl;
	}

	return 0;
}

• Re:我用的是map+欧拉通路 ，这是我的代码，为什么会runtime error？ (86) ashuralyk 2012-05-14 17:03:36