2352371_ac_779ms_740k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INIT (Edge *)malloc(sizeof(Edge))

int n, T;
int m, no;
int stack[10001];
typedef struct node
{
	int adj;
	struct node *next;
}Edge;

int visited[10001];
struct Node
{
	Edge *head;
}Adj[10001];

int bfs(int stauts)
{
	Edge *s;
	int f, r, t;
	int queue[10001], pre[10001];

	f = r = -1;
	queue[++f] = 0;
	pre[0] = -1;
	while(f!=r)
	{
		++r;
		s = Adj[queue[r]].head;
		while(s->next)
		{
			if(!visited[s->next->adj])
			{
				visited[s->next->adj] = 1;
				queue[++f] = s->next->adj;
				pre[s->next->adj] = queue[r];
				if(s->next->adj==T)
				{
					if(stauts)
						return 1;
					goto end;
				}
			}
			s = s->next;
		}
	}
	end:
	if(stauts)
		return 0;
	no = 0;
	for(t = pre[T]; t != -1; t = pre[t])
		stack[no++] = t;
	no--;
	return 0;
}

void solve()
{
	int i, ans;

	ans = no;
	for(i = 0; i < no; i++)
	{
		memset(visited,0,sizeof(visited));
		visited[0] = visited[stack[i]] = 1;
		if(bfs(1))
			ans--;
	}
	printf("%d\n",ans);
}

int main()
{
	long i;
	Edge *t;
	int st, ed;

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
	{
		Adj[i].head = INIT;
		Adj[i].head->next = NULL;
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&st,&ed);
		t = INIT;
		t->adj = ed;
		t->next = Adj[st].head->next;
		Adj[st].head->next = t;
	}
	scanf("%d",&T);
	memset(visited,0,sizeof(visited));
	visited[0] = 1;
	bfs(0);
	solve();
	return 1;
}