提高组精英班 2017清北学堂集训笔记——图论( 六 ) _最小生成树

②从网中删去该节点，并且删去从该节点出发的所有有向边。
③重复以上两步，直到剩余的网中不再存在没有前驱的节点为止。
具体操作过程如下：
若栈非空，则在栈中弹出一个元素，然后枚举这个点能到的每一个点将它的入度-1（删去一条边），如果入度=0，则压入栈中。
如果没有输出所有的顶点，则有向图中一定存在环
1 //拓扑排序，时间复杂度：O(n+m)2 #include 3 #include 4 const int N=100500; 5 const int M=200500; 6 int point[N]={0},to[M]={0},next[M]={0},cc=0; 7 int xu[N]={0};//栈，初始值为空，xu[0]表示栈的大小8 int in[N]={0};//入度，a可以到达b，in[b]++9 int ans[N]={0};//ans[0]整个拓扑序列的大小 10 int n,m; 11 void AddEdge(int x,int y)//邻接表a到b 12 {13cc++;14next[cc]=point[x];15point[x]=cc;16to[cc]=y;17 }18 int main()19 {20int i,j;21scanf("%d%d",&n,&m);22for(i=1;i<=m;i++)23{24int a,b;25scanf("%d%d",&a,&b);26in[b]++;//统计每个节点的入度 27AddEdge(a,b);28}29for(i=1;i<=n;i++)30{31if(in[i]==0)//这个节点入度为0，压入栈 32xu[++xu[0]]=i;33}34while(xu[0])35{36int now=xu[xu[0]];//出栈 37xu[0]--;38ans[++ans[0]]=now;39int ed=point[now];40while(ed)41{42int tox=to[ed];43in[tox]--;44if(!in[tox])45xu[++xu[0]]=tox;46ed=next[ed];//找下一个相邻节点 47}48}49if(ans[0]
八、联通分量：
强连通：有向图中，从a能到b并且从b可以到a，那么a和b强连通。
强连通图：有向图中，任意一对点都满足强连通，则这个图被称为强连通图。
强联通分量：有向图中的极大强连通子图，就是强连通分量。
一般用算法求有向图强连通分量：
推一个蛮容易理解的blog：
九、欧拉路径与哈密顿路径：
1.欧拉路径：从某点出发一笔画遍历每一条边形成的路径。
欧拉回路：在欧拉路径的基础上回到起点的路径（从起点出发一笔画遍历每一条边）。
欧拉路径存在：
无向图：当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。
有向图：当且仅当该图所有顶点出度=入度或者一个顶点出度=入度+1，另一个顶点入度=出度+1，其他顶点出度=入度
欧拉回路存在：
无向图：每个顶点的度数都是偶数，则存在欧拉回路。
有向图：每个顶点的入度都等于出度，则存在欧拉回路。
求欧拉路径/欧拉回路算法常常用算法：
再推一个蛮容易理解的blog：
2.哈密顿路径：每个点恰好经过一次的路径是哈密顿路径。
哈密顿回路：起点与终点之间有边相连的哈密顿路径是哈密顿回路。
最近发现一些网站盗用我的blog，这实在不能忍（?把关于我的名字什么的全部删去只保留文本啥意思。。）！！希望各位转载引用时请注明出处，谢谢配合噢~
【提高组精英班2017清北学堂集训笔记——图论】原博客唯一地址：