题目链接: Brexit
vector 的使用 (vector 存边), 巧用 queue, 相当于 Bfs
- /* */
- # include <iostream>
- # include <cstdio>
- # include <cstring>
- # include <string>
- # include <memory>
- # include <cstdlib>
- # include <cmath>
- # include <climits>
- # include <cctype>
- # include <cassert>
- # include <utility>
- # include <deque>
- # include <queue>
- # include <stack>
- # include <vector>
- # include <bitset>
- # include <set>
- # include <map>
- # include <functional>
- # include <algorithm>
- using namespace std;
- # define lson l,m,rt<<1
- # define rson m+1,r,rt<<1|1
- # define lowbit(x)(x&(-x))
- # define lcm(a,b)(a*b/__gcd(a,b))
- typedef long long ll;
- const ll mod=1e9+7;
- const int maxn=2e5+10;
- const double eps=1e-18;
- const double pi=acos(-1.0);
- int n, m, c, l;
- int de[maxn];
- vector<int>nex[maxn];
- queue<int>qu;
- int flag[maxn];
- int main()
- {
- int t;
- while( ~ scanf("%d%d%d%d", &n, &m, &c, &l) )
- {
- for(int i=1; i<=n; i++ )
- {
- nex[i].clear();
- de[i]=0;
- flag[i]=0;
- }
- while( !qu.empty() )
- qu.pop();
- for(int i=1; i<=m; i++ )
- {
- int u, v;
- scanf("%d%d", &u, &v);
- nex[u].push_back(v);
- nex[v].push_back(u);
- de[u]++;
- de[v]++;
- }
- flag[l]=1;
- qu.push(l);
- while( !qu.empty() )
- {
- int cur=qu.front();
- qu.pop();
- for(int i=0; i<nex[cur].size(); i++ )
- {
- de[nex[cur][i]]--;
- if( de[nex[cur][i]]<=nex[nex[cur][i]].size()/2 && flag[nex[cur][i]]==0 )
- {
- flag[nex[cur][i]] = 1;// 避免重复入栈
- qu.push(nex[cur][i]);
- }
- }
- }
- if( flag[c]==1 )
- cout<<"leave"<<endl;
- else
- cout<<"stay"<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3164739.html