歐拉路與歐拉回路
歐拉路與歐拉回路的定義
如果一張圖中的一個路徑包括每個邊恰好一次，則該路徑稱為歐拉路。
如果一個回路是歐拉路，則稱為歐拉回路。
歐拉路與歐拉回路的存在條件
對于無向聯通圖
歐拉路：只有兩個點為奇點的無向圖存在歐拉路（起點和終點為兩個奇點）。
歐拉回路：沒有奇點的無向圖存在歐拉回路。
對于有向聯通圖
歐拉路：一個頂點的出度-入度=1，另一個頂點的入度-出度=1，其他所有點入度等于出度時存在歐拉路（起點為出度-入度=1的點，終點為入度-出度=1的點）。
歐拉回路：所有點的入度等于出度時存在歐拉回路。
題目:
1.一筆畫問題(NYOJ42)
描述
zyc從小就比較喜歡玩一些小游戲，其中就包括畫一筆畫，他想請你幫他寫一個程序，判斷一個圖是否能夠用一筆畫下來。
規定，所有的邊都只能畫一次，不能重復畫。
輸入
第一行只有一個正整數N(N<=10)表示測試數據的組數。 每組測試數據的第一行有兩個正整數P,Q(P<=1000,Q<=2000)，分別表示這個畫中有多少個頂點和多少條連線。（點的編號從1到P） 隨后的Q行，每行有兩個正整數A,B(0 < A,B < P)，表示編號為A和B的兩點之間有連線。
輸出
如果存在符合條件的連線，則輸出"Yes", 如果不存在符合條件的連線，輸出"No"。
#include<iostream> #include<vector> #include<cstring> using namespace std; const int maxn=1002; vector<int> graph[maxn]; int n,m,cnt,in; bool visited[maxn]; void dfs(int v) { for(int i=0;i<graph[v].size();i++) { int e=graph[v][i]; if(!visited[e]) { cnt++; if(graph[e].size()%2) in++; visited[e]=true; dfs(e); } } } int main() { int t; cin>>t; while (t--) { cin>>n>>m; for(int i=0;i<=n;i++) graph[i].clear(); for(int i=0;i<m;i++) { int x,y; cin>>x>>y; graph[x].push_back(y); graph[y].push_back(x); } cnt=0; in=0; memset(visited,false,sizeof(visited)); dfs(1); if((m==0&&n==1)||(cnt==n&&(in==0||in==2))) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
詳解鏈接：http://www.rzrgm.cn/Lewin671/p/8986270.html
浙公網安備 33010602011771號