Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stdlib.h>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8. using ll = long long;
  9. using ull = unsigned long long;
  10. int cur_component;
  11.  
  12.  
  13. int number_of_ribs(vector<vector<int>> &graph) {
  14.     int result = 0;
  15.     for (int i = 0; i < graph.size(); i++) {
  16.         result += graph[i].size();
  17.     }
  18.     return result;
  19. }
  20.  
  21. void dfs(vector<int> &component, vector<vector<int>> &graph, int v) {
  22.     component[v] = cur_component;
  23.     for (int i = 0; i < graph[v].size(); i++) {
  24.         if (component[graph[v][i]] == 0) {
  25.             dfs(component, graph, graph[v][i]);
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(nullptr);
  33.  
  34.     int N, M;
  35.     cin >> N >> M;
  36.     vector<vector<int>> graph(N);
  37.  
  38.     for (int i = 0; i < M; i++) {
  39.         char part[] = "";
  40.         cin >> part[0];
  41.         int beg, end;
  42.         cin >> beg >> end;
  43.  
  44.         if (strcmp("F", part) == 0) {
  45.             graph[beg - 1].push_back(end - 1);
  46.             graph[end - 1].push_back(beg - 1);
  47.         }
  48.         else {
  49.             for (int j = 0; j < graph[beg - 1].size(); j++) {
  50.                 if (graph[beg - 1][j] == end - 1) {
  51.                     graph[beg - 1].erase(graph[beg - 1].begin() + j);
  52.                 }
  53.             }
  54.             for (int j = 0; j < graph[end - 1].size(); j++) {
  55.                 if (graph[end - 1][j] == beg - 1) {
  56.                     graph[end - 1].erase(graph[end - 1].begin() + j);
  57.                 }
  58.             }
  59.         }
  60.  
  61.         vector<int> visited(N, 0);
  62.         vector<int> component(N, 0);
  63.         cur_component = 1;
  64.        
  65.         for (int j = 0; j < N; j++) {
  66.             if (component[j] != 0) continue;
  67.             dfs(component, graph, j);
  68.             cur_component++;
  69.         }
  70.  
  71.         if ((cur_component - 1 == 1) && (number_of_ribs(graph) / 2 == N - 1)) {
  72.             cout << "YES\n";
  73.         }
  74.         else {
  75.             cout << "NO\n";
  76.         }
  77.     }
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement