首页 > ACM题库 > HDU-杭电 > HDU 3560-Graph’s Cycle Component[解题报告]HOJ
2014
11-05

HDU 3560-Graph’s Cycle Component[解题报告]HOJ

Graph’s Cycle Component

问题描述 :

In graph theory, a cycle graph is an undirected graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain.
Now, you are given a graph where some vertices are connected to be components, can you figure out how many components are there in the graph and how many of those components are cycle graphs.
Two vertices belong to a same component if and only if those two vertices connect each other directly or indirectly.

输入:

The input consists of multiply test cases.
The first line of each test case contains two integer, n (0 < n < 100000), m (0 <= m <= 300000), which are the number of vertices and the number of edges.
The next m lines, each line consists of two integers, u, v, which means there is an edge between u and v.
You can assume that there is no multiply edges and no loops.
The last test case is followed by two zeros, which means the end of input.

输出:

The input consists of multiply test cases.
The first line of each test case contains two integer, n (0 < n < 100000), m (0 <= m <= 300000), which are the number of vertices and the number of edges.
The next m lines, each line consists of two integers, u, v, which means there is an edge between u and v.
You can assume that there is no multiply edges and no loops.
The last test case is followed by two zeros, which means the end of input.

样例输入:

8 9
0 1
1 3
2 3
0 2
4 5
5 7
6 7
4 6
4 7
2 1
0 1
0 0

样例输出:

2 1
1 0

#include<stdio.h>
#include<string.h>
#include<queue>
const int M =100010;
const int maxm=4*M;
struct edge
{
	int to;
	int next;
}e[maxm];
int deta[M];
int vis[M],vos[M];
int num=0;
int head[M];
void addedge(int a,int b)
{
	e[num].to=b;
	e[num].next=head[a];
	head[a]=num++;
}
void init(int n)
{
	num=0;
	for(int i=0;i<n;i++)
	{
		head[i]=-1;
		vis[i]=0;
		vos[i]=0;
		deta[i]=0;
	}
}
void bfs(int k)
{
	std::queue<int> q;
	q.push(k);
	vis[k]=1;
	if(deta[k]!=2)
		vos[k]=1;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=head[tmp];i!=-1;i=e[i].next)
		{
			int to=e[i].to;
			if(!vis[to])
			{
				q.push(to);
				if(deta[to]!=2)
					vos[k]=1;
				vis[to]=1;
			}
		}
	}
}
int main()
{	
	//freopen("graph.in","r",stdin);
	//freopen("out.txt","w",stdout);
	int n,m;
	while(scanf("%d%d",&n,&m),n||m)
	{
		init(n);
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			deta[a]++;
			deta[b]++;
			addedge(a,b);
			addedge(b,a);
		}
		int ans=0,ans2=0;
		for(int i=0;i<n;i++)
			if(!vis[i]) 
			{
				bfs(i);
				ans++;
				if(!vos[i])
					ans2++;
			}
		printf("%d %d\n",ans,ans2);
	}
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c