3142046_ac_0ms_232k.c

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

#include <stdio.h>
#include <string.h>

int n;
int map[101][101];

int dfn[101], low[101], fa[101];
int num;

int min(int a,int b)
{
	return a < b ? a : b;
}

void dfnlow(int u,int v)
{
	int i;

	fa[u] = v;
	dfn[u] = low[u] = num++;
	for(i = 0; i < n; i++)
	{
		if(map[u][i]==1)
		{
			if(dfn[i] < 0)
			{
				dfnlow(i,u);
				low[u] = min(low[u],low[i]);
			}
			else
			{
				if(i != v)
				{
					low[u] = min(low[u],dfn[i]);
				}
			}
		}
	}
}

int main()
{
	int u, v, i, j;
	int no, ans;

	while(scanf("%d",&n)==1,n)
	{
		memset(map,0,sizeof(map));
		while(scanf("%d",&u)==1,u)
		{
			u--;
			while(scanf("%d",&v)==1)
			{
				v--;
				if(u!=v)
				{
					map[u][v] = map[v][u] = 1;
				}
				if(getchar()!=' ')
					break;
			}
		}
		num = 0;
		memset(dfn,-1,sizeof(dfn));
		dfnlow(0,-1);
		no = 0;ans = 0;
		for(i = 1; i < n; i++)
		{
			if(map[0][i]==1&&fa[i]==0)
			{
				no++;
			}
		}
		if(no > 1)
		{
			ans++;
		}
		for(i = 1; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(map[i][j]==1&&low[j]>=dfn[i]&&fa[j]==i)
				{
					ans++;
					break;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}