系統的學習一遍圖論！從這篇博客開始！
先介紹一些概念。
無向圖：
G為連通的無向圖，稱經過G的每條邊一次並且僅一次的路徑為歐拉通路。
如果歐拉通路是回路（起點和終點相同），則稱此回路為歐拉回路。
具有歐拉回路的無向圖G稱為歐拉圖。
有向圖：
D為基圖連通的有向圖，則稱經過D的每一條邊並且僅一次的路徑為有向歐拉通路。
如果該通路是回路，則稱為有向歐拉回路。
具有有向歐拉回路的有向圖D稱為有向歐拉圖。
無向圖判斷歐拉通路：G為連通圖，且僅有兩個奇度的節點或者無奇度節點。
如果有兩個奇度的點，那麼這兩點必定為歐拉通路的起點和終點。
如果沒有奇度的節點，那麼該圖一定有歐拉回路。
有向圖判斷歐拉通路：D的基圖連通，並且所有節點的出度和入度相同，那麼該圖存在有向歐拉回路。
如果僅有兩個節點的出度和入度之差為1和-1，那麼該圖一定存在歐拉通路，並且一定以入度出度之差為-1的點為起點，入度出度之差為1的點為終點。
/************************************************************以上概念******************************************************************/
接下來介紹這道題。
題意就是能否從一個點出發，經過所有的邊，回到節點0。
思路：就是判斷一下，如果起點就是0，那麼就是求是否存在歐拉回路。
如果起點不是0，那麼就是求是否存在歐拉通路，並且歐拉通路的起點終點為0和輸入的起點。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
#define N 1111
char in[111] ;
int degree[N] ;
int main() {
while(cin >> in){
if(in[0] == 'E')break ;
mem(degree , 0) ;
int n , m ;
cin >> n >> m ;
getchar() ;
int sum = 0 ;
for (int i = 0 ; i < m ;i ++ ){
int now ;
gets(in) ;
int l = strlen(in) ;
if(!l)continue ;
int num = 0 ;
for (int j = 0 ;j < l ;j ++ ){
if(in[j] == ' '){
degree[i] ++ ;
degree[num] ++ ;
sum ++ ;
num = 0 ;
}
else {
num = num * 10 + (in[j] - '0') ;
}
}
if(num){
degree[i] ++ ;
degree[num] ++ ;
sum ++ ;
}
}
cin >> in ;
int odd = 0 ;
int even = 0 ;
for (int i = 0 ; i < m ; i ++ ){
if(degree[i] & 1)odd ++ ;
else even ++ ;
}
if(!odd){
if(n == 0){
printf("YES %d\n",sum) ;
}
else {
puts("NO") ;
}
}
else {
if(odd == 2){
if((degree[n] & 1) && (degree[0] & 1) && (n != 0)){
printf("YES %d\n" ,sum) ;
}
else {
puts("NO") ;
}
}else {
puts("NO") ;
}
}
}
return 0 ;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
#define N 1111
char in[111] ;
int degree[N] ;
int main() {
while(cin >> in){
if(in[0] == 'E')break ;
mem(degree , 0) ;
int n , m ;
cin >> n >> m ;
getchar() ;
int sum = 0 ;
for (int i = 0 ; i < m ;i ++ ){
int now ;
gets(in) ;
int l = strlen(in) ;
if(!l)continue ;
int num = 0 ;
for (int j = 0 ;j < l ;j ++ ){
if(in[j] == ' '){
degree[i] ++ ;
degree[num] ++ ;
sum ++ ;
num = 0 ;
}
else {
num = num * 10 + (in[j] - '0') ;
}
}
if(num){
degree[i] ++ ;
degree[num] ++ ;
sum ++ ;
}
}
cin >> in ;
int odd = 0 ;
int even = 0 ;
for (int i = 0 ; i < m ; i ++ ){
if(degree[i] & 1)odd ++ ;
else even ++ ;
}
if(!odd){
if(n == 0){
printf("YES %d\n",sum) ;
}
else {
puts("NO") ;
}
}
else {
if(odd == 2){
if((degree[n] & 1) && (degree[0] & 1) && (n != 0)){
printf("YES %d\n" ,sum) ;
}
else {
puts("NO") ;
}
}else {
puts("NO") ;
}
}
}
return 0 ;
}
