Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 동아리 홍보하기
- #include <cstdio>
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <unordered_map>
- #include <unordered_set>
- #include <fstream>
- #include <cmath>
- #include <ctime>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <functional>
- #include <list>
- #include <deque>
- #include <numeric>
- #include <set>
- #include <climits>
- #include <utility>
- #include <map>
- #include <float.h>
- typedef long long ll;
- typedef unsigned long long ull;
- inline int max( int x, int y ){ return x > y ? x : y ; }
- inline int min( int x, int y ){ return x < y ? x : y ; }
- inline ll max( ll x, ll y ){ return x > y ? x : y ; }
- inline ll min( ll x, ll y ){ return x < y ? x : y ; }
- inline ull max( ull x, ull y ){ return x > y ? x : y ; }
- inline ull min( ull x, ull y ){ return x < y ? x : y ; }
- ll GCD( ll a, ll b ) { return b ? GCD( b , a%b ) : a; }
- using namespace std;
- #define INF 1000000000
- #define MOD 1000000007
- #define PIV 3.14159265358979323846
- #define MAXN 200000
- typedef pair<int, int> P;
- const int MAX_V = 200000;
- int G, H;
- vector<int> adj[MAXN];
- vector<bool> visited;
- const int UNWATCHED = 0;
- const int WATCHED = 1;
- const int INSTALLED = 2;
- int installed;
- int DFS( int here ){
- visited[here] = true;
- int child[3] = { 0, 0, 0 };
- for( int i=0; i<adj[here].size(); ++i ){
- int there = adj[here][i];
- if( !visited[there] ) ++child[DFS(there)];
- }
- if( child[UNWATCHED] ){
- installed++;
- return INSTALLED;
- }
- if( child[INSTALLED] ) return WATCHED;
- return UNWATCHED;
- }
- int Camera(){
- installed = 0;
- visited = vector<bool>(G, false);
- for( int i=0; i<G; ++i ){
- if( !visited[i] && DFS(i) == UNWATCHED ){
- ++installed;
- }
- }
- return installed;
- }
- int main(){
- int A, B;
- scanf("%d %d", &G, &H);
- for( int i=0; i<H; ++i ){
- scanf("%d %d", &A, &B);
- A--; B--;
- adj[A].push_back( B );
- adj[B].push_back( A );
- }
- printf("%d\n", Camera());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement