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 over(int vrchol){ set<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]); } } } if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() >= 0) { // cout<<vrchol<<endl; //cout<<pocet_trojek[komponenty[vrchol]]<<endl; //cout<<mn.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(over(i)){ dasa=true; break; } } } if(dasa) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
--- c5.s755.cteam090.fn.cpp.0.fn.cpp +++ c5.s818.cteam090.fn.cpp.0.fn.cpp @@ -20,5 +20,9 @@ void spust(int vrchol){ - if(hrany[vrchol].size() == 3) pocet_trojek[komponenty[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++){ @@ -44,5 +48,12 @@ } - if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() > 0) return true; + if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() >= 0) { + // cout<<vrchol<<endl; + //cout<<pocet_trojek[komponenty[vrchol]]<<endl; + //cout<<mn.size()<<endl; + return true; + + } + else return false; }