Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <vector> #include <map> using namespace std; typedef struct Node { int polygon; int connects; Node() : polygon(-1), connects(0) {} }; typedef std::vector<Node> Mappp; Mappp mappp; map<int, int> paws; int main() { int n, m; while (scanf("%d %d", &n, &m) == 2) { mappp.clear(); mappp.resize(n+1); int i; for (i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); mappp[a].connects += 1; mappp[b].connects += 1; if (mappp[a].polygon == -1 && mappp[b].polygon == -1) { mappp[b].polygon = a; mappp[a].polygon = a; } if (mappp[a].polygon == -1) { mappp[a].polygon = mappp[b].polygon; } if (mappp[b].polygon == -1) { mappp[b].polygon = mappp[a].polygon; } if (mappp[b].polygon != mappp[a].polygon) { int oldPolygon = mappp[b].polygon; for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) { if (it->polygon == oldPolygon) it->polygon = mappp[a].polygon; } } } bool found = false; paws.clear(); for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) { if (it->connects == 1) paws[it->polygon] += 1; if (paws[it->polygon] >= 4) { found = true; break; } } if (found) printf("YES\n"); else printf("NO\n"); } return 0; }
--- c5.s856.cteam076.fn.cpp.0.fn.cpp +++ c5.s999.cteam076.fn.cpp.0.fn.cpp @@ -1,10 +1,20 @@ #include <stdio.h> #include <stdlib.h> +#include <vector> +#include <map> using namespace std; -typedef int* Map; +typedef struct Node { + int polygon; + int connects; + Node() : polygon(-1), connects(0) {} +}; -Map map; +typedef std::vector<Node> Mappp; + +Mappp mappp; + +map<int, int> paws; int main() @@ -13,6 +23,7 @@ while (scanf("%d %d", &n, &m) == 2) -{ - map = (Map)calloc(n+1, sizeof(int)); +{ + mappp.clear(); + mappp.resize(n+1); int i; @@ -21,23 +32,48 @@ scanf("%d %d", &a, &b); - ++map[a]; - ++map[b]; + mappp[a].connects += 1; + mappp[b].connects += 1; + + if (mappp[a].polygon == -1 && mappp[b].polygon == -1) { + mappp[b].polygon = a; + mappp[a].polygon = a; + } + + if (mappp[a].polygon == -1) { + mappp[a].polygon = mappp[b].polygon; + } + + if (mappp[b].polygon == -1) { + mappp[b].polygon = mappp[a].polygon; + } + + if (mappp[b].polygon != mappp[a].polygon) { + int oldPolygon = mappp[b].polygon; + + for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) { + if (it->polygon == oldPolygon) + it->polygon = mappp[a].polygon; + } + } } - int paws = 0; - for (i = 1; i <= n; ++i) { - //printf("i%d: %d\n", i, map[i]); - if (map[i] == 1) - ++paws; - if (paws >= 4) + bool found = false; + + paws.clear(); + + for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) { + if (it->connects == 1) + paws[it->polygon] += 1; + + if (paws[it->polygon] >= 4) { + found = true; break; + } } - if (paws >= 4) + if (found) printf("YES\n"); else printf("NO\n"); - - free(map); }