Go to diff to previous submission
#include <cstdio> #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <limits.h> #include <map> #include <queue> #include <vector> #include <set> #include <stack> #include <bitset> #include <string> using namespace std; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef set<int> si; typedef set<ii> sii; #define MP make_pair #define PB push_back #define REP(i,a) for ( int i = 0; i < int(a); i++) #define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++) #define FORD(i,a,b) for(int i= int(a); i>=int(b); i--) const int INF = 1<<29; typedef long long int ll; int gn[10001][10001]; int gc[10001]; int is[10001]; int con[10001]; int num,n; int tree,four,ones; void dfs(int x){ int xx; //cout << num << endl; is[x] = 1; //if (gc[x] >= 4) four++; //if (gc[x] >= 3) tree++; if (gc[x] == 1) ones++; REP(i,gc[x]){ xx = gn[x][i]; if( !is[xx] ){ dfs(xx); } } } bool solve(){ REP(i,n){ if(con[i] && !is[i]){ tree = four = ones = 0; dfs(i); //if ( four > 0 || tree > 1)return true; if(ones == 4)return true; } } return false; } int main(){ int m,x,y; while ( scanf("%d%d",&n,&m) == 2){ memset(gc,0,sizeof gc); memset(is,0,sizeof is); memset(con,0,sizeof con); REP(i,m){scanf("%d%d",&x,&y); gn[x][gc[x]++] = y; gn[y][gc[y]++] = x; con[x] = 1; con[y] = 1; } if ( solve() ) printf("YES\n"); else printf("NO\n"); }; return 0; }
--- c5.s796.cteam013.fn.cpp.0.furry.cpp +++ c5.s805.cteam013.fn.cpp.0.furry.cpp @@ -36,5 +36,5 @@ int con[10001]; int num,n; -int tree,four; +int tree,four,ones; void dfs(int x){ @@ -43,7 +43,7 @@ //cout << num << endl; is[x] = 1; - if (gc[x] >= 4) four++; - if (gc[x] >= 3) tree++; - + //if (gc[x] >= 4) four++; + //if (gc[x] >= 3) tree++; + if (gc[x] == 1) ones++; REP(i,gc[x]){ xx = gn[x][i]; @@ -60,7 +60,8 @@ REP(i,n){ if(con[i] && !is[i]){ - tree = four = 0; + tree = four = ones = 0; dfs(i); - if ( four > 0 || tree > 1)return true; + //if ( four > 0 || tree > 1)return true; + if(ones == 4)return true; } }