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) 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 over(int vrchol){ set<int> mn; for(int i= 0; i<hrany[vrchol].size(); i++){ for(int j = 0; j < hrany[vrchol][i]; j++){ int v = hrany[vrchol][i]; if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){ mn.insert(hrany[v][j]); } } } if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() > 0) return true; } 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,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(over(i)){ dasa=true; break; } } } if(dasa) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
--- c5.s705.cteam090.fn.cpp.0.fn.cpp +++ c5.s733.cteam090.fn.cpp.0.fn.cpp @@ -36,5 +36,10 @@ set<int> mn; for(int i= 0; i<hrany[vrchol].size(); i++){ - if(hrany[hrany[vrchol][i]].size()==3) mn.insert(hrany[vrchol][i]); + for(int j = 0; j < hrany[vrchol][i]; j++){ + int v = hrany[vrchol][i]; + if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){ + mn.insert(hrany[v][j]); + } + } }