一行代码生成一棵圣诞树
Python 字符串这块可以玩出很多有意思的功能，今天我以一个精简的字符串打印为例来展示。
一棵小树
print('*'.rjust(3),'* *'.rjust(4),'* * *','|'.rjust(3),sep='\n')
结果：
  *
 * *
* * *
  |
这行代码使用了rjust 函数，实现字符串靠右侧对齐。
它的第一个参数指定字符串的长度，也就是说，'*'.rjust(3) 因为只有一个字符*，显然不够长度3，那么怎么办，默认用空格从左侧开始填充2个空格，此时长度不就是3个字符吗！
再需要注意：print 的 sep 这个关键字参数，指明前面几个参数的分割符号。
这棵树不带色彩，那么有没有办法变出一颗五彩斑斓的小树呢？
一颗带颜色树
print("\033[5;35;40m"+'*'.rjust(3)+"\033[0m",'* *'.rjust(4),'* * *','|'.rjust(3),sep='\n')
结果：
这是怎么做到的？与第一节相比，只是多了几个字符："\033[5;35;40m"，怎么解读？\033[ 可理解为格式化打印的前缀，其他字符含义：5表示显示方式为闪烁，35表示前景色为洋红，40m表示背景色为黑色
1、显示方式：
0（默认）、1（高亮）、22（非粗体）、4（下划线）、24（非下划线）、 5（闪烁）、25（非闪烁）、7（反显）、27（非反显）

2、前景色：
30（黑色）、31（红色）、32（绿色）、 33（×××）、34（蓝色）、35（洋 红）、36（青色）、37（白色）

3、背景色:
40（黑色）、41（红色）、42（绿色）、 43（×××）、44（蓝色）、45（洋 红）、46（青色）、47（白色）
如何做到五彩斑斓？第二、三行分别选用其他前景色：
print("\033[5;35;40m"+'*'.rjust(3)+"\033[0m","\033[5;36;40m"+'* *'.rjust(4)+"\033[0m","\033[5;46;40m* * *\033[0m","\033[5;35;40m"+'|'.rjust(3)+"\033[0m",sep='\n')
原创不易，欢迎点个在看

                

注意文字意思：不管是生成树还是最小生成树一定还是输，千万别和图混淆了。

下面来说生成树：我们这棵树是针对图来说的，如果你们已经知道极小连通子图就非常简单了， 

极小连通子图什么意思呢，就是我们把图中的全部节点连接起来，假如n个节点那么，边是n - 1条。

注意形成的一定是一棵树才是生成树。

好了回到正题： 

  那么我们的生成树怎么在图的基础上生成的呢？ 

  我们学了图应该知道有2种遍历方法：1深度优先遍历  2广度优先遍历 

  深度优先遍历（DFS）是什么意思呢：假定一个起点比如下图所示： 


假如我知道0的地址，我们使用深度优先遍历算法遍历当前的图： 

分析：深度字面意思一定要搞定这个意思就是说我们根据当前节点访问当前节点的一个孩子，然后在访问孩子节点的一个孩子节点，一直递归下去。直到全部节点访问完毕就停止访问，否则我们就退到上个节点从另一个孩子节点开始使用相同方式访问孩子节点。 


分析：由深度优先遍历算法得到的生成树如上图；

我们从起点0开始，找到0的第一个邻节点2， 因此0->2->3->4->1->5. 

这个序列是确定的吗，在这个图是确定的，先0我们在找邻节点我们假如在逆时针方位开始0开始找到第一个邻节点也就是2并且都标为访问过然后就找到2的邻节点3 在就是4在就是1，这个时候是不是有4个方位，但是只有5没有访问因此就是5 这个时候全部访问完毕。

第二个办法就是广度优先算法生成树：



分析：我们来看看这个生成树是怎么形成的， 我们还是0开始，标志为被访问， 

然后由于是广度优先访问全部的邻节点在访问孩子的全部邻节点 0->2   1  5   3  4

现在引入我们的最小生成树的定义：既然是最小在是生成树的基础上，在加上假如是带权值，那么生成树的很多种当中必有一个生成树权值和是最小，那么最小那棵树就是最小生成树。

那么权值是什么意思，比如0节点和2节点之间我们可以看成是一个城市到一个城市的车费或者路程。 

那么最小就是走遍全部城市的车费或者路程最小。

T1是一棵含有几百万个节点的树，T2含有几百个节点。判断T2是否是T1 的子树。
首先考虑小数据量的情况，可以根据树的前序和中序遍历所得的字符串，来通过判断T2生成的字符串是否是T1字符串的子串，来判断T2是否是T1的子树。假设T1的节点数为N，T2的节点数为M。遍历两棵树算法时间复杂性是O(N + M)， 判断字符串是否为另一个字符串的子串的复杂性也是O( N + M)（比如使用KMP算法）。所需要的空间也是O(N + M)。
这里有一个问题需要注意：对于左节点或者右节点为null的情况，需要在字符串中插入特殊字符表示。否则对于下面这种情形将会判断错误：
因此如果插入特殊字符，上述两棵树的中序和前序遍历的结果是相同的。
由于本例有几百万的节点，需要占用O(N + M)的内存。
如果换一种思路，就是遍历T1，每当T1的某个节点与T2的根节点值相同时，就判断两棵子树是否相同。这个算法的复杂度是O(N*M)。我们再仔细思考一下。因为只有在节点值与T2的根节点值相同才会调用O(M)。假设有K次这种情况，那么算法的复杂度就是O(N + K*M)。下面是代码实现：

struct TreeNode{
	TreeNode *leftChild;
	TreeNode *rightChild;
	int data;
};
// check sub tree n1 == sub tree n2
 bool checkSubTree(const TreeNode* n1, const TreeNode* n2){
	if( n1 == nullptr && n2 == nullptr )
		return true;
	
	if( n1 == nullptr || n2 == nullptr )
		return false;
	
	if( n1->data != n2->data )
		return false;
	
	return checkSubTree(n1->leftChild, n2->leftChild) && checkSubTree(n1->rightChild, n2->rightChild);
}
bool subTree(const TreeNode *n1, const TreeNode *n2){
	if( n1 == nullptr){
		return false; // the bigger tree is empty, so t2 is not subtree of t1
	}
	
	if( n1->data == n2->data){
		if( checkSubTree(n1, n2))
			return true;
	}
	
	return subTree(n1->leftChild, n2) || subTree(n2->rightChild, n2);
}
 


对于上面讨论的2种解法，哪种解法比较好呢？其实有必要好好讨论一番：

1）方法一会占用O(N + M)的内存，而另外一种解法只会占用O(logN + logM)的内存（递归的栈内存）。当考虑scalability扩展性时，内存使用的多寡是个很重要的因素。
2）方法一的时间复杂度为O(N + M)，方法二最差的时间复杂度是O(N*M)。所以要通过工程实践或者是历史数据看一下哪种方法更优。当然了，方法二也可能会很早发现两棵树的不同，早早的退出了checkSubTree。
总的来说，在空间使用上，方法二更好。在时间上，需要通过实际数据来验证。

在存在权值相等的边时，最小生成树可能有多个。话不多说，求它个数的方法如下：

先用Prim生成最小树，同时记录边的关系。用并查集表示//不要压缩路径



让每个元素都指向它的父亲节点。

找出权值相同的边，去除树上的这条边，一棵树就被砍成了两颗，然后看加上另一条是否能连接这科树



方法就是这样，复杂度O(|E|log|E|)



具体问题：



输入

第一行：T //代表T组数据 

每组数据：

V E //代表V个顶点 E条边
E行x y z//代表节点x到y的边长
输出

最小生成树的个数



代码

#include<stdio.h>
#include<algorithm>
#include<queue>
#define MAX_V 102
#define MAX_E 10002
using namespace std;
struct cell{int x,y,cost;};
int par[MAX_V];
bool used[MAX_V];
cell cs[MAX_E],vs[MAX_V];//保存最小生成树的边
int E,V;

//不要压缩路径 通过并查集表示生成树
void init(int n){for(int i=0;i<=n;i++) par[i]=i;}
int find(int x){return x==par[x]?x:find(par[x]);}
void unite(int x,int y){par[y]=x;}
bool same(int x,int y){return find(x)==find(y);}

bool cmp(cell a,cell b){return a.cost<b.cost;}
bool operator < (cell a,cell b){return a.cost>b.cost;}
int prim(){
    fill(used,used+V+1,false);
    init(V);
    priority_queue<cell> que;
    que.push({1,1,0});
    int u=0;

    while(!que.empty()){
        cell e=que.top();que.pop();
        int t=e.y;
        if(used[t]) continue;
        used[t]=true;
        unite(e.x,e.y);
        vs[u++]=e;

        for(int i=0;i<E;i++)//这儿可以用其他数据结构优化
            if(cs[i].x==t&&!used[cs[i].y])
                que.push({t,cs[i].y,cs[i].cost});
    }

    E/=2;
    sort(cs,cs+E,cmp);
    sort(vs,vs+V,cmp);
    int j=0,k=0,N=1;
    while(j<E&&k<V){
        int va=cs[j].cost,vb=vs[k].cost;
        if(va==vb){
            if(!(cs[j].x==vs[k].x&&cs[j].y==vs[k].y)){
                par[vs[k].y]=vs[k].y;//断开
                if(!same(cs[j].x,cs[j].y)) N++;
                par[vs[k].y]=vs[k].x;//接上
            }
            j++;
        }else if(va<vb){
            j++;
        }else{
            k++;
        }
    }
    return N;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&V,&E);
        for(int i=0;i<E;i++){
            scanf("%d%d%d",&cs[i].x,&cs[i].y,&cs[i].cost);
            cs[E+i].y=cs[i].x;
            cs[E+i].x=cs[i].y;
            cs[E+i].cost=cs[i].cost;
        }
        E*=2;
        int ans=prim();
        printf("%d\n",ans);
    }
    return 0;
}