fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector< vector< int > > edges(1000005);
  4. bool visited[1000005];
  5. int component[1000005];
  6. void dfs(int node, int num_component){
  7.     visited[node] = true;
  8.     component[node] = num_component;
  9.     for(int i = 0 ; i < (int)edges[node].size(); i++){
  10.         int curr = edges[node][i];
  11.         if(!visited[curr]){
  12.             dfs(curr, num_component);
  13.         }
  14.     }
  15.     return;
  16. }
  17. int main(){
  18.     int t;
  19.     cin >> t;
  20.     while(t--){
  21.         int n, k;
  22.         cin >> n >>k;
  23.         for(int i = 0; i <= n; i++){
  24.             edges[i].clear();
  25.             visited[i] = false;
  26.         }
  27.         vector<pair<int, int>> check;
  28.         for(int i = 0; i < k; i++){
  29.             int x, y;
  30.             char ch1, ch2;
  31.             cin >> x >> ch1;
  32.             if(ch1 == '!'){
  33.                 cin >> ch2 >> y;
  34.                 check.push_back(make_pair(x, y));
  35.             }
  36.             else{
  37.                 cin >> y;
  38.                 edges[x].push_back(y);
  39.                 edges[y].push_back(x);
  40.             }
  41.         }
  42.         int num_component = 1;
  43.         for(int i=1; i <=n ; i++){
  44.             if(!visited[i]){
  45.                 dfs(i, num_component);
  46.                 num_component++;
  47.             }
  48.         }
  49.         bool flag = true;
  50.         for(int i = 0; i < (int)check.size(); i++){
  51.             int src = check[i].first;
  52.             int target = check[i].second;
  53.             if(component[src] == component[target]){
  54.                 flag = false;
  55.                 break;
  56.             }
  57.         }
  58.         if(flag){
  59.             cout<<"YES\n";
  60.         }
  61.         else{
  62.             cout<<"NO\n";
  63.         }
  64.     }
  65. }
Success #stdin #stdout 0.01s 26368KB
comments (?)
stdin
copy 
2
2 2
1 = 2
1 != 2
3 2
1 = 2
2 != 3
stdout
copy 
NO
YES
https://ideone.com/jl7C1a
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!