图找环算法

‘壹’ 鍒ゆ柇缁椤畾镄勫浘鏄钖︽槸链夊悜镞犵幆锲1

鍒ゆ柇镞犲悜锲句腑鏄钖﹀瓨鍦ㄥ洖璺锛堢幆锛夌殑绠楁硶鎻忚堪
濡傛灉瀛桦湪锲炶矾锛屽垯蹇呭瓨鍦ㄤ竴涓瀛愬浘锛屾槸涓涓鐜璺銆傜幆璺涓镓链夐《镣圭殑搴>=2銆
绠楁硶锛
绗涓姝ワ细鍒犻櫎镓链夊害<=1镄勯《镣瑰强鐩稿叧镄勮竟锛屽苟灏嗗彟澶栦笌杩欎簺杈圭浉鍏崇殑鍏跺畠椤剁偣镄勫害鍑忎竴銆
绗浜屾ワ细灏嗗害鏁板彉涓1镄勯《镣规帓鍏ラ槦鍒楋纴骞朵粠璇ラ槦鍒椾腑鍙栧嚭涓涓椤剁偣閲嶅嶆ラや竴銆
濡傛灉链钖庤缮链夋湭鍒犻櫎椤剁偣锛屽垯瀛桦湪鐜锛屽惁鍒欐病链夌幆銆
链夊悜锲炬槸钖︽湁鐜镄勫垽瀹氱畻娉曪纴涓昏佹湁娣卞害浼桦厛鍜屾嫇镓戞帓搴2涓鏂规硶銆
𨰾撴墤鎺掑簭锛屽傛灉鑳藉熺敤𨰾撴墤鎺掑簭瀹屾垚瀵瑰浘涓镓链夎妭镣圭殑鎺掑簭镄勮瘽锛屽氨璇存槑杩欎釜锲句腑娌℃湁鐜锛岃屽傛灉涓嶈兘瀹屾垚锛屽垯璇存槑链夌幆銆

‘贰’ 初中数学如何画树状图

最小树形图,就是给有向带权图中指定一个特殊的点v,求一棵有向生成树T,使得该有向树的根为v,并且T中所有边的总权值最小.最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法.
判断是否存在树形图的方法很简单,只需要以v为根作一次图的遍历就可以了,所以下面的算法中不再考虑树形图不存在的情况.
在所有操作开始之前,我们需要把图中所有的自环全都清除.很明显,自环是不可能在任何一个树形图上的.只有进行了这步操作,总算法复杂度才真正能保证是O(VE).
首先为除根之外的每个点选定一条入边,这条入边一定要是所有入边中最小的.现在所有的最小入边都选择出来了,如果这个入边集不存在有向环的话,我们可以 证明这个集合就是该图的最小树形图.这个证明并不是很难.如果存在有向环的话,我们就要将这个有向环所称一个人工顶点,同时改变图中边的权.假设某点u在 该环上,并设这个环中指向u的边权是in[u],那么对于每条从u出发的边(u, i, w),在新图中连接(new, i, w)的边,其中new为新加的人工顶点; 对于每条进入u的边(i, u, w),在新图中建立边(i, new, w-in[u])的边.为什么入边的权要减去in[u],这个后面会解释,在这里先给出算法的步骤.然后可以证明,新图中最小树形图的权加上旧图中被收缩 的那个环的权和,就是原图中最小树形图的权.
上面结论也不做证明了.现在依据上面的结论,说明一下为什么出边的权不变,入边的权要减去in [u].对于新图中的最小树形图T,设指向人工节点的边为e.将人工节点展开以后,e指向了一个环.假设原先e是指向u的,这个时候我们将环上指向u的边 in[u]删除,这样就得到了原图中的一个树形图.我们会发现,如果新图中e的权w'(e)是原图中e的权w(e)减去in[u]权的话,那么在我们删除 掉in[u],并且将e恢复为原图状态的时候,这个树形图的权仍然是新图树形图的权加环的权,而这个权值正是最小树形图的权值.所以在展开节点之后,我们 得到的仍然是最小树形图.逐步展开所有的人工节点,就会得到初始图的最小树形图了.
如果实现得很聪明的话,可以达到找最小入边O(E),找环 O(V),收缩O(E),其中在找环O(V)这里需要一点技巧.这样每次收缩的复杂度是O(E),然后最多会收缩几次呢?由于我们一开始已经拿掉了所有的 自环,我门可以知道每个环至少包含2个点,收缩成1个点之后,总点数减少了至少1.当整个图收缩到只有1个点的时候,最小树形图就不不用求了.所以我们最 多只会进行V-1次的收缩,所以总得复杂度自然是O(VE)了.由此可见,如果一开始不除去自环的话,理论复杂度会和自环的数目有关.

‘叁’ 天干地支年月日时算法是什么

方法1、六十环周推算法

方法：已知某年年干支，根据六十环周图次序推算。

举例：已知2016年（春节后）为丙申年，求2020年干支。

解答：在表中找到丙申，向后推四年，可知2020年（春节后）为庚子年。

方法2、公式计算法

方法：求某年年干支，公式为（当年年数-3）÷60，其余数为所求年干支的代数，再到六十环周图中找出相应的干支。年数减3，是因为公元4年恰好是甲子年，从公元4年起，就要减去公元4年前的3年，故该公式适用于公元4年之后。

举例：求1979年的干支。

解答：（1979-3）÷60=32······56，在六十环周图中找到56对应的干支，可知1979年为己未年。

注意：

天干地支，简称为干支，源自中国远古时代对天象的观测。十干是指阏逢、旃蒙、柔兆、强圉、着雍、屠维、上章、重光、玄黓、昭阳。十二支是指困敦、赤奋若、摄提格、单阏、执徐、大荒落、敦牂、协洽、涒滩、作噩、阉茂、大渊献。

简化后的天干地支：“甲、乙、丙、丁、戊、己、庚、辛、壬、癸”称为十天干，“子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥”称为十二地支。

十天干和十二地支依次相配，组成六十个基本单位，两者按固定的顺序相互配合，组成了干支纪元法。天干地支的发明影响深远，依旧在使用天干地支，用于历法、术数、计算、命名等各方面。

‘肆’ 无向图中查找环的算法有哪些

比较直观的办法是，从初始结点 S 开始，用深度优先的方法遍历图的结点，如果在这个过程中，你遇到了一个先前就已经发现过的结点（假定它叫 V），说明存在一个环。
如果你想输出这个环，那么就从 V 沿路返回，直到又遇到 V，途中经过的所有结点就组成了这个环。

‘伍’ 设计算法判断一个无向图G是否为树。

首先题目中有一中吵处应该是错了。

第2到n+1行，应该改为，第2到m+1行

方法：DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。该算法的复杂度为O(V)。

代码：

/*
设计算法判断一个无向图G是否为树。若是，输出“Yes！”；否则输出“No！”。
输入格式：
第1行是空格分隔的两个整数n和m，分别表示无向图的顶点数和边数，n<=10000,m<=100000。
第2到m+1行，每行两个整数a和b，表示顶点a和b之间有一条边，1<=a,b<=n。
键盘输入，不必检查输者乱入错误，输入确保正确。
输出格式：
屏幕上显示一行，“yes！”或“no！”.行末有回车。

样例1

样例卖嫌侍2

输入：
43
12
23
31
输出：
No！

输入：
21
12

输出：
Yes！
*/

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

constintN=10000,M=100000;
booledge[N][N];//数组记录两点是否存在边
boolvisit[N];//标记该节点是否访问过

boolDFS_check(intx,inty=-1)
{
	if(visit[x])
		returnfalse;

	visit[x]=true;
	inti;
	for(i=0;i<N;i++)
		if(edge[x][i]&&i!=y)
			if(visit[i])
				returnfalse;
			else
				if(!DFS_check(i,x))
					returnfalse;

	returntrue;
}

intmain()
{
	intn,m;
	scanf("%d%d",&n,&m);
	
	memset(edge,false,sizeof(edge));
	inti,x,y;
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		edge[x-1][y-1]=true;
		edge[y-1][x-1]=true;
	}

	memset(visit,false,sizeof(visit));
	boolresult=DFS_check(0);
	if(result)
		for(i=0;i<n;i++)
			if(!visit[i])
				result=false;
	if(result)
		printf("Yes!
");
	else
		printf("No!
");

	system("pause");
	return0;
}