The Great Revegetation

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("revegetate.in", "r", stdin);
	freopen("revegetate.out", "w", stdout);
 
	int n, m;
	cin >> n >> m;
 
	vector<vector<pair<int, bool>>> adj(n);
 
	for (int i = 0; i < m; i++) {
		char type;
		int u, v;
		cin >> type >> u >> v;
 
		adj[--u].push_back({--v, type == 'S'});
		adj[v].push_back({u, type == 'S'});
	}
 
	int component_num = 0;
	bool impossible = false;
	vector<int> color(n, -1);
 
	for (int i = 0; i < n; i++) {
		// aún no visitamos este nodo.
		if (color[i] == -1) {
			component_num++;
 
			queue<pair<int, bool>> todo;
			todo.push({i, true});
 
			while (!todo.empty()) {
				// procesamos el siguiente nodo
				pair<int, bool> nxt = todo.front();
				todo.pop();
 
				// fijamos el tipo de pasto de nxt.first
				color[nxt.first] = nxt.second;
 
				// recorremos los nodos adyacentes
				for (pair<int, bool> u : adj[nxt.first]) {
					bool type = u.second ? nxt.second : !nxt.second;
 
					// no visitado
					if (color[u.first] == -1) {
						todo.push({u.first, type});
						// genera una contradicción
					} else if (color[u.first] == !type) {
						impossible = true;
						break;
					}
				}
			}
		}
	}
 
	if (impossible) {
		cout << 0 << endl;
	} else {
		// 2^component_num en binario es 1, seguido de component_num ceros.
		cout << 1;
		for (int i = 0; i < component_num; i++) { cout << 0; }
		cout << endl;
	}
}

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Revegetate {
	public static int[] type;
	public static boolean impossible;
	public static ArrayList<Integer>[] same;
	public static ArrayList<Integer>[] diff;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("revegetate.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("revegetate.out"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
 
		type = new int[N + 1];
		same = new ArrayList[N + 1];
		diff = new ArrayList[N + 1];
 
		// Inicializamos las listas de adyacencia.
		for (int i = 0; i <= N; i++) {
			same[i] = new ArrayList<>();
			diff[i] = new ArrayList<>();
		}
		int comps = 0;  // El número de componentes conexas.
 
		// Leemos las aristas.
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			char type = st.nextToken().charAt(0);
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
 
			// Comparten el mismo tipo de pasto
			if (type == 'S') {
				same[a].add(b);
				same[b].add(a);
			}
			// Comparten tipos de pasto distintos.
			if (type == 'D') {
				diff[a].add(b);
				diff[b].add(a);
			}
		}
 
		for (int i = 1; i <= N; i++) {
			// Este nodo no está visitado, así que intentamos colorearlo con el color '1'.
			if (type[i] == 0) {
				visit(i, 1);
				comps++;
			}
		}
		// Es imposible colorear los campos.
		if (impossible) {
			pw.println(0);
		} else {
			// La solución es 2^(número de componentes).
			pw.print(1);
			for (int i = 0; i < comps; i++) { pw.print(0); }
			pw.println();
		}
		pw.close();
	}
 
	// Visitamos un nodo y lo coloreamos.
	public static void visit(int node, int color) {
		type[node] = color;
 
		// Revisamos todos los nodos que deberían compartir el mismo color.
		for (int next : same[node]) {
			// Hay una contradicción aquí.
			if (type[next] == 3 - color) { impossible = true; }
			if (type[next] == 0) { visit(next, color); }
		}
 
		// Revisamos todos los nodos que deberían tener un color distinto.
		for (int next : diff[node]) {
			// Hay una contradicción aquí.
			if (type[next] == color) { impossible = true; }
			if (type[next] == 0) { visit(next, 3 - color); }
		}
	}
}