Advertisement
Guest User

Untitled

a guest
Oct 21st, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.85 KB | None | 0 0
  1. // 동아리 홍보하기
  2.  
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cstring>
  7. #include <unordered_map>
  8. #include <unordered_set>
  9. #include <fstream>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <vector>
  13. #include <stack>
  14. #include <queue>
  15. #include <functional>
  16. #include <list>
  17. #include <deque>
  18. #include <numeric>
  19. #include <set>
  20. #include <climits>
  21. #include <utility>
  22. #include <map>
  23. #include <float.h>
  24. typedef long long ll;
  25. typedef unsigned long long ull;
  26. inline int max( int x, int y ){ return x > y ? x : y ; }
  27. inline int min( int x, int y ){ return x < y ? x : y ; }
  28. inline ll max( ll x, ll y ){ return x > y ? x : y ; }
  29. inline ll min( ll x, ll y ){ return x < y ? x : y ; }
  30. inline ull max( ull x, ull y ){ return x > y ? x : y ; }
  31. inline ull min( ull x, ull y ){ return x < y ? x : y ; }
  32. ll GCD( ll a, ll b ) { return b ? GCD( b , a%b ) : a; }
  33. using namespace std;
  34. #define INF 1000000000
  35. #define MOD 1000000007
  36. #define PIV 3.14159265358979323846
  37. #define MAXN 200000
  38. typedef pair<int, int> P;
  39. const int MAX_V = 200000;
  40.  
  41. int G, H;
  42. vector<int> adj[MAXN];
  43. vector<bool> visited;
  44. const int UNWATCHED = 0;
  45. const int WATCHED = 1;
  46. const int INSTALLED = 2;
  47. int installed;
  48.  
  49. int DFS( int here ){
  50. visited[here] = true;
  51. int child[3] = { 0, 0, 0 };
  52. for( int i=0; i<adj[here].size(); ++i ){
  53. int there = adj[here][i];
  54. if( !visited[there] ) ++child[DFS(there)];
  55. }
  56.  
  57. if( child[UNWATCHED] ){
  58. installed++;
  59. return INSTALLED;
  60. }
  61.  
  62. if( child[INSTALLED] ) return WATCHED;
  63. return UNWATCHED;
  64. }
  65.  
  66. int Camera(){
  67. installed = 0;
  68. visited = vector<bool>(G, false);
  69. for( int i=0; i<G; ++i ){
  70. if( !visited[i] && DFS(i) == UNWATCHED ){
  71. ++installed;
  72. }
  73. }
  74. return installed;
  75. }
  76.  
  77. int main(){
  78.  
  79. int A, B;
  80. scanf("%d %d", &G, &H);
  81. for( int i=0; i<H; ++i ){
  82. scanf("%d %d", &A, &B);
  83. A--; B--;
  84. adj[A].push_back( B );
  85. adj[B].push_back( A );
  86. }
  87. printf("%d\n", Camera());
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement