Source code for submission s1143

Go to diff to previous submission

fn.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include<cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <string>
  13. #include <vector>
  14.  
  15. using namespace std;
  16.  
  17. #define REP(i,n) for ( int i = 0; i < (n); i++)
  18. #define FOR(i,a,b) for ( int i = (a); i <= (b); i++ )
  19. #define FORD(i,a,b) for ( int i = (a); i>= (b); i-- )
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21.  
  22. queue<int> q;
  23.  
  24. bool bunny;
  25. int grade[10024];
  26. bool visited [10024];
  27. int sib[10024][10024];
  28. int sibCnt[10024];
  29. int p1, p2, points, lines,res;
  30.  
  31. void dfs (int node, bool first) {
  32. 	int cnt = 0;
  33. 	if (visited[node]) return;
  34. 	if (first && sibCnt[node]==1) res++;
  35. 	bool found = false;
  36. 	visited[node] = true;
  37. 	//DEBUG(sibCnt[node]);
  38. 	for (int i = 0; i < sibCnt[node]; i++)	{
  39. 		if (!visited[sib[node][i]]) {
  40. 			if (first) cnt++;
  41. 			//cout << "Node " << sib[node][i] << endl;
  42. 			dfs (sib[node][i],false);
  43. 			found = true;
  44. 		}
  45. 	}
  46. 	if (first && cnt==1) res++;
  47. 	if (!found) res++;	
  48. }
  49.  
  50.  
  51. void bfs (int node) {
  52. 	bool found = false;
  53. 	if (sibCnt[node] == 1) res++;
  54. 	q.push(node);
  55. 	while(!q.empty()) {
  56. 		found = false;
  57. 		node = q.front(); q.pop();
  58. 		visited[node] = true;
  59. 		REP(i, sibCnt[node]) {
  60. 			if (!visited[sib[node][i]]) {
  61. 				q.push(sib[node][i]);
  62. 				found = true;
  63. 			}
  64. 		}
  65. 		if (!found) res++;
  66. 	}
  67. 	//DEBUG(res);
  68. }
  69.  
  70. int main() {
  71.  
  72. 	while(scanf("%d%d",&points,&lines) == 2) {
  73. 		bunny=false;
  74. 		REP(i,points+10) {
  75. 			visited[i]=false;
  76. 			sibCnt[i] = 0;
  77. 			grade[i] = 0;
  78. 		}
  79. 		REP(i,lines) {
  80. 			scanf("%d%d",&p1,&p2);
  81. 			sib[p1][sibCnt[p1]++] = p2;
  82. 			sib[p2][sibCnt[p2]++] = p1;
  83. 			grade[p1]++;
  84. 			grade[p2]++;
  85. 		}
  86. 		FOR(i,1,points) {
  87. 			FOR(j,1,points) visited[i]=false;
  88. 			res = 0;
  89. 			//bfs(i);
  90. 			dfs(i,true);
  91. 			if (res >= 4 || grade[i] >= 4) {
  92. 				bunny = true;
  93. 				break;
  94. 			}
  95. 		}
  96. 		//cout << endl;
  97. 		if (bunny) cout << "YES" << endl;
  98. 		else cout << "NO" << endl;
  99. 	}
  100. 	return 0;
  101. }
  102.  

Diff to submission s1104

fn.cpp

--- c5.s1104.cteam027.fn.cpp.0.fn.cpp
+++ c5.s1143.cteam027.fn.cpp.0.fn.cpp
@@ -28,5 +28,5 @@
 int sibCnt[10024];
 int p1, p2, points, lines,res;
-/*
+
 void dfs (int node, bool first) {
         int cnt = 0;
@@ -45,15 +45,12 @@
         }
         if (first && cnt==1) res++;
-        if (!found) res++;
-        
-        
+        if (!found) res++;      
 }
-*/
+
 
 void bfs (int node) {
         bool found = false;
-        if (visited[node]) return;
-        q.push(node);
         if (sibCnt[node] == 1) res++;
+        q.push(node);
         while(!q.empty()) {
                 found = false;
@@ -90,5 +87,6 @@
                         FOR(j,1,points) visited[i]=false;
                         res = 0;
-                        bfs(i);
+                        //bfs(i);
+                        dfs(i,true);
                         if (res >= 4 || grade[i] >= 4) {
                                 bunny = true;