歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一潭訓路，現給定一個無向圖，問是否存在歐拉回路？
輸入格式:
輸入第一行給出兩個正整數，分別是節點數N (1≤N≤1000)和邊數M；隨后的M行對應M條邊，每行給出一對正整數，分別是該條邊直接連通的兩個節點的編號（節點從1到N編號），
輸出格式:
若歐拉回路存在則輸出1，否則輸出0，
輸入樣例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6
輸出樣例1:
1
輸入樣例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4
輸出樣例2:
0
解題程序：
歐拉回路要求：
（1）所有頂點度為偶數；//鄰接矩陣很適合統計度
（2）圖連通，（可用并查集）
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 1000
typedef int Vertex;
typedef struct MGNode *MGraph;
struct MGNode{
int Nv;
int Ne;
int G[MaxVertexNum][MaxVertexNum];
};
typedef struct ENode *Edge;
struct ENode{
Vertex V1,V2;
};
MGraph CreateGraph(int N){
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct MGNode));
Graph->Nv = N;
Graph->Ne = 0;
Vertex V,W;
for(V=0; V<Graph->Nv;V++){
for(W=0; W<Graph->Nv; W++){
Graph->G[V][W] = 0;
}
}
return Graph;
}
void InsertEdge(MGraph Graph, Edge E){
/**插入無向邊**/
Graph->G[E->V1-1][E->V2-1] = 1;
Graph->G[E->V2-1][E->V1-1] = 1;
}
MGraph BuildGraph(){
int N;
scanf("%d",&N);
MGraph Graph;
Graph = CreateGraph(N);
scanf("%d",&(Graph->Ne));
if(Graph->Ne){
Edge E = (Edge)malloc(sizeof(struct ENode));
int i;
for(i=0;i<Graph->Ne;i++){
scanf("%d %d",&E->V1,&E->V2);
InsertEdge(Graph, E);
}
}
return Graph;
}
int CheckDegree(MGraph Graph){
int Degree[MaxVertexNum];
int i,j;
for(i=0;i<Graph->Nv;i++){
Degree[i] = 0;
}
int flag = 0;/**標志位 0-度為偶數，1-度為奇數**/
for(i=0;i<Graph->Nv;i++){
for(j=0;j<Graph->Nv;j++){
Degree[i] += Graph->G[i][j];//由于是無向邊 ，對稱，只需考慮行
}
//printf("i:%d %d\n",i,Degree[i]);
/**判斷是否為偶數邊**/
if(Degree[i]%2!=0){
flag = 1;
break;
}
}
if(flag) return 0;
else
return 1;
}
int Visited[MaxVertexNum];
int DST(MGraph Graph, Vertex V, int cnt){
Visited[V] = 1;
//printf("1\n");
if(cnt == Graph->Nv){
/*若cnt等于頂點數，圖連通*/
return 1;
}
else{
Vertex W;
int flag;
for(W=0;W<Graph->Nv; W++){
if(!Visited[W]&&Graph->G[V][W]>0){
cnt++;
flag = DST(Graph, W, cnt);
/*已確定圖已連通，快速跳出*/
//printf("%d\n",flag);
if(flag){
break;
}
}
}
return flag;
}
}
int GraphCycle(MGraph Graph){
Vertex V,W;
int flag=0;
for(V=0;V<Graph->Nv;V++){
for(W=0;W<Graph->Nv;W++){
Visited[W]=0;
}
if(DST(Graph,V, 1)){
flag = 1;
break;
}
}
if(flag)
return 1;
else
return 0;
}
int main()
{
MGraph Graph;
Graph = BuildGraph();
if(CheckDegree(Graph)&&GraphCycle(Graph)){
printf("1");
}
else
printf("0");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/75822.html
標籤：其他
上一篇：spark vector 和 breeze自帶的vector
下一篇：堆疊的應用----括號匹配