题意简述:给出一个有向图,问从s出发是否能找到一条长度为奇数的路径并且路径的端点出度为0,存在就输出路径,如果不存在判断图中是否存在环,存在输出Draw,否则输出lose
题解:类似于DP,将每一个点拆成两个点,d[x][0]=1表示存在一条s到x存在一条长度为奇数的路径,d[x][1]相反,然后正常bfs计算就好了
判环什么的都是小意思
#include<bits/stdc++.h> #define forn(i, n) for (int i = 0 ; i < int(n) ; i++) #define fore(i, s, t) for (int i = s ; i < (int)t ; i++) #define fi first #define se second #define all(x) x.begin(),x.end() #define pf2(x,y) printf("%d %d\n",x,y) #define pf(x) printf("%d\n",x) #define each(x) for(auto it:x) cout<<it<<endl; #define pii pair<int,int> using namespace std; typedef long long ll; const int maxn=1e5+5; const int maxm=2e5+5; const int inf=1e9; int n,m,s; vector<int> g[maxn],ig[maxn]; int d[maxn][2],pre[maxn][2],vis[maxn]; bool dfs(int x){ vis[x]=1; for(auto y:g[x]) if(vis[y]==1 || dfs(y)) return 1; vis[x]=2; return 0; } int main(){ cin>>n>>m; queue<pair<int,int>> q; for(int i=1;i<=n;i++){ int x=i,y; int cc; cin>>cc; while(cc--){ cin>>y; g[x].push_back(y); ig[y].push_back(x); } if(g[x].size()==0) q.push({x,1}); } while(q.size()){ pii x=q.front();q.pop(); for(auto y:ig[x.fi]){ if(d[y][x.se^1]==0) { d[y][(x.se)^1]=1; pre[y][(x.se)^1]=x.fi; q.push({y,(x.se)^1}); } } } cin>>s; if(d[s][0]){ puts("Win"); vector<int> ans; ans.push_back(s); int p=s,px=0; while(pre[p][px]){ p=pre[p][px],px^=1; ans.push_back(p); } for(int i=0;i<ans.size();i++) cout<<ans[i]<<‘ ‘; cout<<"\n"; } else { if(dfs(s)) puts("Draw"); else puts("Lose"); } }
原文:https://www.cnblogs.com/033000-/p/12347325.html