SHARE
TWEET

Untitled

a guest Oct 21st, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top