2010723_ac_15ms_68k.c

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

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXV 210
# define MAXE 260
typedef struct node
{
	int id;
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MAXV];
typedef struct ALGraph
{
	AdjList adjlist;
}Graphic;

int n;
int mark;
int ans;
int count;
int F, R;
int visited[MAXE];
int bridge[MAXE];
int pre[MAXV];
int low[MAXV];
Graphic G;

struct bnode
{
	int v;
	int w;
}Bridge[MAXE];

void init()
{
	int i;

	scanf("%d%d",&F,&R);
	ans = count = n = 0;
	memset(pre,-1,sizeof(pre));
	memset(bridge,0,sizeof(bridge));
	for(i = 0; i < F; i++)
		G.adjlist[i].firstedge = NULL;
}

void dfs(int v)
{
	EdgeNode *s;

	visited[v] = 1;
	s = G.adjlist[v].firstedge;
	while(s)
	{
		if(mark)
			return ;
		if(visited[s->adjvex]==0)
		{
			if(bridge[s->adjvex])
				mark = 1;
			else
				dfs(s->adjvex);	
		}
		s = s->next;
	}
	return ;
}

void dfs_bridge(int w, int id)
{
	int v;
	EdgeNode *s;

	pre[w] = low[w] = count++;
	s = G.adjlist[w].firstedge;
	while(s)
	{
		if(pre[v=s->adjvex]==-1)
		{
			dfs_bridge(v,s->id);
			if(low[w]>low[v])
				low[w] = low[v];
			if(low[v]==pre[v])
			{
				//printf("%d-%d\n",w,v);
				bridge[v] = bridge[w] = 1;
				Bridge[n].w = w;
				Bridge[n].v = v;
				n++;
			}
		}
		else
			if(s->id!=id&&low[w]>pre[v])
				low[w] = pre[v];
		s = s->next;
	}
}

void input()
{
	int i;
	int w, v;
	EdgeNode *s;

	for(i = 0; i < R; i++)
	{
		scanf("%d%d",&w,&v);
		w--;v--;
		s = (EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex = v;
		s->id = i;
		s->next = G.adjlist[w].firstedge;
		G.adjlist[w].firstedge = s;
		s = (EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex = w;
		s->id = i;
		s->next = G.adjlist[v].firstedge;
		G.adjlist[v].firstedge = s;
	}
}

void solve()
{
	int i;

	for(i = 0; i < n; i++)
	{
		mark = 0;
		memset(visited,0,sizeof(visited));
		visited[Bridge[i].w] = 1;
		dfs(Bridge[i].v);
		if(!mark)
			ans++;
		mark = 0;
		memset(visited,0,sizeof(visited));
		visited[Bridge[i].v] = 1;
		dfs(Bridge[i].w);
		if(!mark)
			ans++;
	}
	printf("%d",(ans+1)/2);
}

int main()
{
	init();
	input();
	dfs_bridge(0,G.adjlist[0].firstedge->id);
	solve();
	return 1;
}