1980757_ac_0ms_56k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 161 行

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MaxVertexNum 28

int di[27];
int dj[27];
char output[27];
int mark[26][27];
int t[26][27];
typedef struct node
{
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	int degree;
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct ALGraph
{
	AdjList adjlist;
	int n, e;
}Graphic;

int cmp(const void *a, const void *b)
{
	return *(int *)a-*(int *)b;
}

void init(Graphic *G)
{
	int i;

	for(i = 0; i < G->n; i++)
	{
		G->adjlist[i].firstedge = NULL;
		G->adjlist[i].degree = 0;
	}
}

void topsort(Graphic *G,int n)
{
	int i, j, l, top;
	int stack[100];
	EdgeNode *s;

	top = l = 0;
	for(i = 0; i < n; i++)
		if(G->adjlist[i].degree==0)
		{
			top++;
			stack[top] = i;
		}
	while(top)
	{
		i = stack[top];
		top--;
		output[l++] = i+'A';
		s = G->adjlist[i].firstedge;
		while(s)
		{
			j = s->adjvex;
			G->adjlist[j].degree--;
			if(G->adjlist[j].degree==0)
			{
				top++;
				stack[top] = j;
			}
			s = s->next;
		}
	}
	//printf("l is %d\n",l);
}

void input()
{
	int k, sum;
	int i, j, n, m;
	int wrong, pos;
	char tmp[4];
	Graphic G;
	EdgeNode *s;

	while(scanf("%d%d",&n,&m)==2&&n&&m)
	{
		G.n = n; G.e = m;
		init(&G);
		pos = wrong = sum = 0;
		memset(mark,0,sizeof(mark));
		memset(t,0,sizeof(t));
		for(i = 0; i < m; i++)
		{
			scanf("%s",tmp);
			if(wrong||pos)
				continue;
			sum = 0;
			if(tmp[0]==tmp[2]||mark[tmp[2]-'A'][tmp[0]-'A'])
			{
				wrong = i+1;
				continue;
			}
			else
			{
				if(t[tmp[0]-'A'][tmp[2]-'A']==0)
				{
					t[tmp[0]-'A'][tmp[2]-'A'] = 1;
					s = (EdgeNode *)malloc(sizeof(EdgeNode));
					s->adjvex = tmp[2]-'A';
					s->next = G.adjlist[tmp[0]-'A'].firstedge;
					G.adjlist[tmp[0]-'A'].firstedge = s;
					G.adjlist[tmp[2]-'A'].degree++;
				}
				mark[tmp[0]-'A'][tmp[2]-'A'] = 1;
				for(j = 0; j < n; j++)
				{
					if(mark[tmp[2]-'A'][j])
						mark[tmp[0]-'A'][j] = 1;
					if(mark[j][tmp[0]-'A'])
						mark[j][tmp[2]-'A'] = 1;
				}
				for(j = 0; j < n; j++)
				{
					for(k = 0; k < n; k++)
					{
						sum += mark[j][k];
				//		printf("%d ",mark[j][k]);
					}
				//	printf("\n");
				}
				//printf("sum is %d\n",sum);
				if(sum==n*(n-1)/2)
				{
					pos = i+1;
					topsort(&G,n);
				}
			}
		}
		if(wrong)
			printf("Inconsistency found after %d relations.\n",wrong);
		else
			if(pos)
			{
				printf("Sorted sequence determined after %d relations: ",pos);
				for(i = 0; i < n; i++)
					printf("%c",output[i]);
				printf(".\n");
			}
			else
				printf("Sorted sequence cannot be determined.\n");
	}
}

int main()
{
	input();
	return 1;
}