Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- long long component = 0;
- bool impossible = false;
- vector<pair<int, char>> adj[100001];
- bool visited[100001];
- bool color[100001];
- bool isDiag = false;
- void dfs(int u, bool g){
- visited[u] = true;
- color[u] = g;
- for (auto v: adj[u]){
- if(visited[v.first]){
- if(v.second == 'S' && color[v.first] != g) impossible = true;
- if(v.second == 'D' && color[v.first] == g) impossible = true;
- }
- if(!visited[v.first]){
- if(v.second == 'S') dfs(v.first, g);
- else dfs(v.first, !g);
- }
- }
- }
- int main()
- {
- //isDiag = true;
- freopen("revegetate.in", "r", stdin);
- int n, m;
- cin >> n >> m;
- if(isDiag) cout << "n: " << n << ", m: " << m << endl;
- for(int i = 0; i < m; ++i){
- char a;
- int b, c;
- cin >> a >> b >> c;
- adj[b].push_back({c, a});
- adj[c].push_back({b, a});
- }
- for(int i = 1; i <= n; ++i){
- if(!visited[i]){
- component++;
- dfs(i, 0);
- }
- if(impossible) break;
- }
- if(!isDiag) freopen("revegetate.out", "w", stdout);
- if(impossible) cout << 0 << endl;
- else{
- cout << 1;
- while(component--){
- cout << 0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
