#include<bits/stdc++.h>
using namespace std;
const int n_max = 5 * 1e5+7;
int leader[n_max];
vector<int> zone;
vector<int> zone_status;
vector<int> zone_size;
int find_zone(int v){
if(zone[v] != v){
zone[v] = find_zone(zone[v]);
}
return zone[v];
}
int find(int v){
return find_zone(leader[v]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
int last = 0;
zone.push_back(0);
zone_status.push_back(0); // 0 - brak, 1 - nieznane, 2 - pewne
zone_size.push_back(0);
for(int i = 0; i < q; i++){
char operation;
cin >> operation;
// Add new element
if(operation == '+'){
int a, b;
cin >> a >> b;
int zone_a = find(a);
int zone_b = find(b);
if(zone_status[zone_a] < zone_status[zone_b]){
swap(a, b);
swap(zone_a, zone_b);
}
// Zupelnie nowa przestzren
if(zone_status[zone_a] == 0){
last++;
zone.push_back(last);
zone_status.push_back(1);
zone_size.push_back(2);
leader[a] = last;
leader[b] = last;
if(a == b){
zone_status[last] = 2;
}
continue;
}
// Dodanie, ktore nic nie zmienia
if(zone_status[zone_b] == 0){
zone_size[zone_a]++;
leader[b] = zone_a;
continue;
}
// Jesli laczymy ta sama strefe
if(zone_a == zone_b){
zone_status[zone_a] = 2;
continue;
}
zone[zone_b] = zone_a;
zone_size[zone_a] += zone_size[zone_b];
}
// Eliminate element
if(operation == '-'){
int a;
cin >> a;
int zone_a = find(a);
zone_size[zone_a]--;
if(zone_size[zone_a] == 1 and zone_status[zone_a] == 1){
zone[zone_a] = 0;
}
leader[a] = 0;
}
// Question
if(operation == '?'){
int a;
cin >> a;
int zone_a = find(a);
if(zone_status[zone_a] == 0){
cout << 0;
}
if(zone_status[zone_a] == 1){
cout << '?';
}
if(zone_status[zone_a] == 2){
cout << 1;
}
}
}
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include<bits/stdc++.h> using namespace std; const int n_max = 5 * 1e5+7; int leader[n_max]; vector<int> zone; vector<int> zone_status; vector<int> zone_size; int find_zone(int v){ if(zone[v] != v){ zone[v] = find_zone(zone[v]); } return zone[v]; } int find(int v){ return find_zone(leader[v]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; int last = 0; zone.push_back(0); zone_status.push_back(0); // 0 - brak, 1 - nieznane, 2 - pewne zone_size.push_back(0); for(int i = 0; i < q; i++){ char operation; cin >> operation; // Add new element if(operation == '+'){ int a, b; cin >> a >> b; int zone_a = find(a); int zone_b = find(b); if(zone_status[zone_a] < zone_status[zone_b]){ swap(a, b); swap(zone_a, zone_b); } // Zupelnie nowa przestzren if(zone_status[zone_a] == 0){ last++; zone.push_back(last); zone_status.push_back(1); zone_size.push_back(2); leader[a] = last; leader[b] = last; if(a == b){ zone_status[last] = 2; } continue; } // Dodanie, ktore nic nie zmienia if(zone_status[zone_b] == 0){ zone_size[zone_a]++; leader[b] = zone_a; continue; } // Jesli laczymy ta sama strefe if(zone_a == zone_b){ zone_status[zone_a] = 2; continue; } zone[zone_b] = zone_a; zone_size[zone_a] += zone_size[zone_b]; } // Eliminate element if(operation == '-'){ int a; cin >> a; int zone_a = find(a); zone_size[zone_a]--; if(zone_size[zone_a] == 1 and zone_status[zone_a] == 1){ zone[zone_a] = 0; } leader[a] = 0; } // Question if(operation == '?'){ int a; cin >> a; int zone_a = find(a); if(zone_status[zone_a] == 0){ cout << 0; } if(zone_status[zone_a] == 1){ cout << '?'; } if(zone_status[zone_a] == 2){ cout << 1; } } } return 0; } |
English