对于连通图
无向图:1.无奇点,可以从任意一点出发回到原点。 2.存在奇点,且只有两个,从一奇点出发,另一奇点终止。
有向图:1.所有点入度等于出度。 2.只有两个点入度不等于出度,且其中一个点入度比出度大一另一个点的出度比入度大一。
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> #include <string> #include <iostream> using namespace std; int s,n; int ans[1000]; int ret; void solve() { char str[1000]; for(int i=0;i<n;i++){ cin.getline(str,100); int len=strlen(str); for(int j=0;j<len;j++){ if(str[j]!=‘ ‘){ ans[i]++; ret++; int k=str[j]-‘0‘;ans[k]++; } } } cin.getline(str,100); int a=0;int b=0; for(int i=0;i<n;i++){ if(ans[i]&1) a++; else b++; } if(a==0&&s==0) cout<<"YES "<<ret<<endl; else if(a==2&&s!=0&&ans[s]&1&&ans[0]&1) cout<<"YES "<<ret<<endl; else cout<<"NO"<<endl; } int main() { char str[1000];char str1[1000]; while(cin.getline(str,100)){ ret=0; memset(ans,0,sizeof(ans)); if(str[0]==‘S‘){ sscanf(str,"%s%d%d",str1,&s,&n); solve(); } else break; } return 0; }
原文:http://www.cnblogs.com/yigexigua/p/3850900.html