Go to diff to previous submission
#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <set> #include <string> #include <cmath> #include <algorithm> #include <queue> using namespace std; int n,m; int komponent = 1; vector<vector<int> > hrany; vector<int> komponenty; vector<int> pocet_trojek; void spust(int vrchol){ if(hrany[vrchol].size() == 3) { //cout<<"tri u: "<<vrchol+1<<endl; pocet_trojek[komponenty[vrchol]]++; } for(int i = 0; i<hrany[vrchol].size(); i++){ if(komponenty[hrany[vrchol][i]]==-1){ komponenty[hrany[vrchol][i]] = komponent; spust(hrany[vrchol][i]); } } } bool dvojica(int u, int v){ set<int> mnD; for(int i = 0; i<hrany[u].size(); i++){ if(hrany[u][i]!=v) mnD.insert(hrany[u][i]); } for(int i = 0; i<hrany[v].size(); i++){ if(hrany[v][i]!=u) mnD.insert(hrany[v][i]); } if(mnD.size()>=4) return false; else return true; } bool over(int vrchol){ multiset<int> mn; for(int i= 0; i<hrany[vrchol].size(); i++){ for(int j = 0; j < hrany[hrany[vrchol][i]].size(); j++){ int v = hrany[vrchol][i]; if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){ mn.insert(hrany[v][j]); } } } multiset<int>::iterator it = mn.begin(); set<int> mnFin; while(it!=mn.end()){ if(mn.count(*it)>=2) mnFin.insert(*it); it++; } for(int i=0; i< hrany[vrchol].size(); i++){ int v = hrany[vrchol][i]; if(hrany[v].size()==3 && dvojica(v,vrchol)){ mnFin.insert(v); } } /*if (vrchol==2){ cout<<vrchol<<endl; cout<<hrany[vrchol].size()<<endl; cout<<pocet_trojek[komponenty[vrchol]]<<endl; cout<<mn.size()<<endl; cout<<mnFin.size()<<endl; }*/ if(pocet_trojek[komponenty[vrchol]] - 1 - mnFin.size() > 0) { /* cout<<vrchol<<endl; cout<<hrany[vrchol].size()<<endl; cout<<pocet_trojek[komponenty[vrchol]]<<endl; cout<<mn.size()<<endl; cout<<mnFin.size()<<endl;*/ return true; } else return false; } int main () { while(scanf("%d%d",&n,&m)!= EOF){ hrany.clear(); hrany.resize(n); komponenty.clear(); komponenty.resize(n,-1); pocet_trojek.clear(); pocet_trojek.resize(n+5,0); while(m--){ int a,b; scanf("%d%d",&a,&b); a--; b--; hrany[a].push_back(b); hrany[b].push_back(a); } komponent = 1; bool bolo = false; for(int i = 0; i<n; i++){ if(hrany[i].size() >= 4) { cout<<"YES"<<endl; bolo = true; } } if(bolo) continue; for(int i = 0; i < n; i++){ if(komponenty[i]==-1) { komponenty[i]=komponent; spust(i); komponent++; } } bool dasa=false; for(int i = 0; i < n; i++){ if(pocet_trojek[komponenty[i]] > 1){ if(hrany[i].size()>=3 && over(i)){ dasa=true; break; } } } if(dasa) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
--- c5.s818.cteam090.fn.cpp.0.fn.cpp +++ c5.s870.cteam090.fn.cpp.0.fn.cpp @@ -37,6 +37,21 @@ } +bool dvojica(int u, int v){ + set<int> mnD; + for(int i = 0; i<hrany[u].size(); i++){ + if(hrany[u][i]!=v) + mnD.insert(hrany[u][i]); + } + for(int i = 0; i<hrany[v].size(); i++){ + if(hrany[v][i]!=u) + mnD.insert(hrany[v][i]); + } + + if(mnD.size()>=4) return false; + else return true; +} + bool over(int vrchol){ - set<int> mn; + multiset<int> mn; for(int i= 0; i<hrany[vrchol].size(); i++){ for(int j = 0; j < hrany[hrany[vrchol][i]].size(); j++){ @@ -48,8 +63,35 @@ } - if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() >= 0) { - // cout<<vrchol<<endl; - //cout<<pocet_trojek[komponenty[vrchol]]<<endl; - //cout<<mn.size()<<endl; + multiset<int>::iterator it = mn.begin(); + + set<int> mnFin; + + while(it!=mn.end()){ + if(mn.count(*it)>=2) mnFin.insert(*it); + it++; + } + + for(int i=0; i< hrany[vrchol].size(); i++){ + int v = hrany[vrchol][i]; + if(hrany[v].size()==3 && dvojica(v,vrchol)){ + mnFin.insert(v); + } + } + + /*if (vrchol==2){ + + cout<<vrchol<<endl; + cout<<hrany[vrchol].size()<<endl; + cout<<pocet_trojek[komponenty[vrchol]]<<endl; + cout<<mn.size()<<endl; + cout<<mnFin.size()<<endl; + }*/ + + if(pocet_trojek[komponenty[vrchol]] - 1 - mnFin.size() > 0) { + /* cout<<vrchol<<endl; + cout<<hrany[vrchol].size()<<endl; + cout<<pocet_trojek[komponenty[vrchol]]<<endl; + cout<<mn.size()<<endl; + cout<<mnFin.size()<<endl;*/ return true; @@ -98,5 +140,5 @@ for(int i = 0; i < n; i++){ if(pocet_trojek[komponenty[i]] > 1){ - if(over(i)){ + if(hrany[i].size()>=3 && over(i)){ dasa=true; break;