蓝桥杯算法入

不带权图算法（topo排序）欧拉通路与欧拉回路

不带权图算法 ：
对一个有向无环图 G进行 拓扑排序
利用前驱图 先从第一个没有前驱的起点开始遍历
理解：其它顶点 有一个入度 标记值++ ，每次有入度的边的顶点 出队列时 ，就标记值-- ，为0时可以当前顶点可以入队 ，全部出队结束遍历

拓扑排序算法：
1.选择一个入度为0 的顶点并将它输出；
2.删除图中从顶点连出的所有边.

循环结束，若输出的顶点数小于图中的顶点数，则表示该图中存在回路， 也就是无法进行拓扑排序
常见性质应用： 如 ①是 ②的前驱 ， 可以想成 ①小于 ②

( ① – > ②)
输入：
4 3
1 2
3 2
2 4
输出：
1
3
2
4

*/

#include 
using namespace std; 


#include
#include

const int MAX_N = 100;
const int MAX_M = 10000;
struct edge{
	int v,next;  //顶点 ，下一条边 
	int len;  //长度 
	
} E[MAX_M];  //名E 的结构体数组 

int p[MAX_N],eid;  

void init(){
	memset(p,-1,sizeof(p));  
	eid = 0;
}

void insert(int u,int v){
	E[eid].v = v;  
	E[eid].next = p[u];  
	p[u] = eid++;
}

int n,m; 
int indegree[MAX_N]; //存放每个顶点的 入度 

void topo(){
	queue q;
	for(int i = 1;i <= n;i++){
		if(indegree[i] == 0){ //入度减为0 ，入队 
			q.push(i); 
		} 
	}
	while(!q.empty()){
		int now = q.front();
		cout << now << endl;
		q.pop();
		for(int i = p[now];i != -1;i = E[i].next){  //遍历到最后一条边  （E结构体数组 初始值为-1） 
			int v = E[i].v;
			indegree[v]--;
			if(indegree[v] == 0){
				q.push(v);
			}
		}
	} 
}

void test_01(){
	init();
	memset(indegree,0,sizeof(indegree));
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		int u,v;
		cin >> u >> v;
		insert(u,v);
		indegree[v]++;
	}
	topo(); 
	return;
}

七桥问题（无向图） --（一笔画 / 欧拉回路）

无向图是否具有欧拉通路或回路的判定: （欧拉通路 ∈欧拉回路 ）
:图连通；图中只有0个或2个度为奇数的节点 （0个时也是欧拉回路）
欧拉回路:图连通；图中所有节点度均为偶数

有向图是否具有欧拉通路或回路的判定:
欧拉通路:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1 或 所有节点入度等于出度 （入 == 出 时也是欧拉回路）
欧拉回路:图连通；所有节点入度等于出度

练习题 (待更新)
当拓扑排序有多个解时，要求字典序最小的优先排序 --用优先队列 ，每次取队列中值最小的

//如何输出欧拉回路    P32  1.53h 


int main() {
	test_01();
	return 0;
}