图的关节点.txt

ACM资料大集合

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

#define NMAX 100
//求图的关节点
/*
输入：
10 12
1 3
1 2
2 3
3 4
4 5
4 6
5 7
6 7
7 8
8 9
8 10
9 10
输出
8 7 4 3
*/
bool visited[NMAX];
bool path[NMAX][NMAX];
int pre[NMAX];
int beta[NMAX];
int ans[NMAX];
int anscount;
int cixu;//第几次dfs
int start;//根
int rootgre;//根的儿子数

int min(int a,int b)
{
	if(a<b) return a;
	else return b;
}
void dfs(int v,int num)
{//v是当前点，num是总共点
	int w;
	bool isarc;
	visited[v]=true;
	beta[v]=pre[v]=++cixu;
	isarc=false;
	for(w=1;w<=num;w++)
	{
		if(path[v][w]==true)
		{
			if(visited[w]==false)
			{//v->w是树边
				dfs(w,num);
				if(v==start) 
				{
					rootgre++;
					if(rootgre==2) isarc=true;
				}
				else
				{
					beta[v]=min(beta[v],beta[w]);
					if(beta[w]>=pre[v]) isarc=true;
				}
			}
			else
			{//v->w是回边
				beta[v]=min(beta[v],pre[w]);
			}
		}
	}
	if(isarc==true) ans[++anscount]=v;
}

int init(int num)
{
	int i,j;
	cixu=anscount=rootgre=0;
	start=1;
	for(i=1;i<=num;i++)
	{
		visited[i]=false;
		for(j=1;j<=num;j++)
			path[i][j]=false;
	}	
}

int main()
{
	int i,num,pnum,a,b;
	scanf("%d %d",&num,&pnum);
	init(num);
	for(i=1;i<=pnum;i++)
	{
		scanf("%d %d",&a,&b);
		path[a][b]=path[b][a]=true;
	}
	dfs(start,num);
	for(i=1;i<=anscount;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}