Source code for submission s705

fn.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. int n,m;
  15.       int komponent = 1;
  16.  
  17.     vector<vector<int> >  hrany;
  18.     vector<int> komponenty;
  19.     vector<int> pocet_trojek;
  20.  
  21. void spust(int vrchol){
  22.   if(hrany[vrchol].size() == 3) pocet_trojek[komponenty[vrchol]]++;
  23.  
  24.   for(int i = 0; i<hrany[vrchol].size(); i++){
  25.     if(komponenty[hrany[vrchol][i]]==-1){
  26.  
  27. 	komponenty[hrany[vrchol][i]] = komponent;
  28. 	spust(hrany[vrchol][i]);
  29.     }
  30.  
  31.   }
  32.  
  33. }    
  34.  
  35. bool over(int vrchol){
  36.   set<int> mn;
  37.   for(int i= 0; i<hrany[vrchol].size(); i++){
  38.     if(hrany[hrany[vrchol][i]].size()==3) mn.insert(hrany[vrchol][i]);
  39.   }
  40.  
  41.   if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() > 0) return true;
  42. }
  43.  
  44. int main () {
  45.   while(scanf("%d%d",&n,&m)!= EOF){
  46.     hrany.clear();
  47.     hrany.resize(n);
  48.     komponenty.clear();
  49.     komponenty.resize(n,-1);
  50.     pocet_trojek.clear();
  51.     pocet_trojek.resize(n,0);
  52.     while(m--){
  53.       int a,b;
  54.       scanf("%d%d",&a,&b);
  55.       a--; b--;
  56.  
  57.       hrany[a].push_back(b);
  58.       hrany[b].push_back(a);
  59.     }
  60.       komponent = 1;
  61.  
  62.       bool bolo = false;
  63.       for(int i = 0; i<n; i++){
  64. 	if(hrany[i].size() >= 4) {
  65. 	  cout<<"YES"<<endl;
  66. 	 bolo = true;
  67. 	}
  68.       }
  69.  
  70.       if(bolo) continue;
  71.  
  72.       for(int i = 0; i < n; i++){
  73. 	if(komponenty[i]==-1) {
  74. 	  komponenty[i]=komponent;
  75. 	  spust(i);
  76. 	  komponent++;
  77. 	}
  78.       }
  79.  
  80.       bool dasa=false;
  81.  
  82.       for(int i = 0; i < n; i++){
  83. 	if(pocet_trojek[komponenty[i]] > 1){
  84. 	  if(over(i)){
  85. 	    dasa=true;
  86. 	    break;
  87. 	  }
  88. 	}
  89.       }
  90.  
  91.       if(dasa) cout<<"YES"<<endl;
  92.       else cout<<"NO"<<endl;
  93.     }
  94.  
  95.  
  96. }