Go to diff to previous submission
#include <vector> #include <list> #include <map> #include <set> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <string> #include <queue> #define vi vector <int> #define vl vector <long long> #define vpii vector <pair <int,int> > #define mp(x,y) make_pair(x,y) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define FOR(i,n) for(ll i=0;i<int(n);i++) #define READ(v,n) {FOR(i,n){ll x;cin>>x;v.pb(x);} } #define gmin(a,b) {if (b<a) a=b;} #define gmax(a,b) {if (b>a) a=b;} #define pb push_back #define ppb pop_back typedef long long ll; typedef unsigned long long ull; using namespace std; int main(){ int n, m; while(cin>>n>>m){ vi v; vector <vi> edges(n,v); vi es(n,0); FOR(i,m){ int x,y; cin>>x>>y; edges[x-1].pb(y-1); edges[y-1].pb(x-1); es[x-1]++; es[y-1]++; } FOR(i,n){ vi used(n,0); vpii q; // priority_queue <int> q; vi edgesize=es; q.pb(mp(i,n-sz(edges[i]))); FOR(j,edges[i].size()){edgesize[edges[i][j]]--;} used[i]=1; while(q.size()!=0){ if(q.size()>=4){cout<<"YES"<<endl;goto end;} pair <int,int> y=q[q.size()-1]; q.ppb(); int x=y.first; FOR(j,edges[x].size()){ int next=edges[x][j]; if(used[next]==0){ edgesize[next]--; FOR(k,sz(edges[next])){ edgesize[edges[next][k]]--; } q.pb(mp(next,edgesize[next])); int w=0; while(w<sz(q) && q[w].second<edgesize[next]) w++; q.insert(q.begin()+w,mp(next,edgesize[next])); used[next]=1; } } } } cout<<"NO"<<endl; end: } return 0; }
--- c5.s664.cteam012.fn.cpp.0.fn.cpp +++ c5.s858.cteam012.fn.cpp.0.fn.cpp @@ -77,8 +77,7 @@ } cout<<"NO"<<endl; - + end: } - end: return 0; }