题目链接：点击打开链接
题目大意：给一个无向图，判断给出的任意两点（注意起点等于终点的情况）是否存在一条经过的边数为奇数的路径。
解题思路：略。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; int n,m,flag,s,e; int vis[maxn]; vector<int> v[maxn]; void init() { for(int i=0;i<n;i++) { vis[i]=0; v[i].clear(); } } void dfs(int s,int k) { if(flag) return; if(s==e) { if(k%2==1) flag=1; return; } for(int i=0;i<v[s].size();i++) { int idx=v[s][i]; if(!vis[idx]) { vis[idx]=1; dfs(idx,k+1); vis[idx]=0; } } } int main() { while(~scanf("%d%d",&n,&m)) { init(); int q; for(int i=0;i<m;i++) { scanf("%d%d",&s,&e); v[s].push_back(e); v[e].push_back(s); } scanf("%d",&q); while(q--) { flag=0; scanf("%d%d",&s,&e); if(s==e) { puts("No"); continue; } dfs(s,0); if(flag) puts("Yes"); else puts("No"); } } return 0; }
