Closing the Farm

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{DSU}
struct DSU {
	vector<int> e;
	DSU(int N) : e(N, -1) {}
 
	// obtener el representante de la componente (usa compresión de caminos)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
	bool same_set(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	// unión por tamaño
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
// EndCodeSnip
 
int main() {
	freopen("closing.in", "r", stdin);
	int n, m;
	cin >> n >> m;
 
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	// conn[i] = si la i-ésima granja está cerrada
	vector<bool> conn(n);
	vector<int> rev(n);
	for (int i = 0; i < n; i++) {
		cin >> rev[i];
		rev[i]--;
	}
 
	DSU dsu(n);
	reverse(rev.begin(), rev.end());
 
	conn[rev[0]] = 1;
	// un nodo siempre está conectado
	vector<string> ans = {"YES"};
 
	// componentes conexas
	int cc = 1;
	for (int i = 1; i < n; i++) {
		cc++;
		conn[rev[i]] = 1;
		for (int j : adj[rev[i]]) {
			if (conn[j]) {
				if (dsu.unite(j, rev[i])) { cc--; }
			}
		}
		ans.push_back(cc == 1 ? "YES" : "NO");
	}
	reverse(ans.begin(), ans.end());
 
	freopen("closing.out", "w", stdout);
	for (const string &i : ans) { cout << i << '\n'; }
}

# BeginCodeSnip{Disjoint Set Union}
class DisjointSetUnion:
	def __init__(self, num_nodes: int) -> None:
		self.parent = [*range(num_nodes)]
		self.size = [1] * num_nodes
 
	def find_parent(self, v: int) -> int:
		if self.parent[v] == v:
			return v
		self.parent[v] = self.find_parent(self.parent[v])
		return self.parent[v]
 
	def union(self, a: int, b: int) -> bool:
		a = self.find_parent(a)
		b = self.find_parent(b)
		if a == b:
			return False
		if self.size[a] < self.size[b]:
			a, b = b, a
		self.parent[b] = a
		self.size[a] += self.size[b]
		return True
 
	def connected(self, a: int, b: int) -> bool:
		return self.find_parent(a) == self.find_parent(b)
 
 
# EndCodeSnip
 
with open("closing.in", "r") as infile:
	n, m = map(int, infile.readline().split())
	graph = [[] for _ in range(n)]
	for _ in range(m):
		f, t = map(lambda i: int(i) - 1, infile.readline().split())
		graph[f].append(t)
		graph[t].append(f)
	remove_order = [int(infile.readline()) - 1 for _ in range(n)]
 
dsu = DisjointSetUnion(n)
 
"""
Simulamos abrir la granja en el orden inverso al de cerrarla. Para cada granero,
lo abrimos, y luego lo conectamos a cualquier granero adyacente abierto, todo
mientras contamos la cantidad de componentes conexas.
"""
 
open_barns = set()
components = 0
fully_connected = []
 
for node in remove_order[::-1]:
	components += 1
	for adj in graph[node]:
		if adj in open_barns:
			if dsu.union(adj, node):
				components -= 1
 
	fully_connected.append("YES" if components == 1 else "NO")
	open_barns.add(node)
 
print(*fully_connected[::-1], sep="\n", file=open("closing.out", "w"))

import java.io.*;
import java.util.*;
 
public class closing {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("closing.in"));
		PrintWriter out = new PrintWriter("closing.out");
 
		int n = sc.nextInt();
		int m = sc.nextInt();
 
		ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
		for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); }
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		int[] order = new int[n];
		for (int i = 0; i < n; i++) { order[i] = sc.nextInt() - 1; }
 
		UnionFind graph = new UnionFind(n);
		boolean[] open = new boolean[n];
		ArrayList<String> answers = new ArrayList<>();
 
		// Procesar los cierres en orden inverso:
		// En lugar de cerrar cada granja, simulamos abrir granjas
		for (int i = n - 1; i >= 0; i--) {
			open[order[i]] = true;
 
			// Conectar la granja que se abre con el vecino sii está abierta
			for (int neighbor : adj.get(order[i])) {
				if (open[neighbor]) { graph.union(order[i], neighbor); }
			}
			// Poner la respuesta en YES si la cantidad de componentes conexas
			// es igual a graneros no abiertos + 1 (por la componente formada por los graneros abiertos)
			if (graph.components == i + 1) {
				answers.add("YES");
			} else {
				answers.add("NO");
			}
		}
 
		Collections.reverse(answers);
		for (int i = 0; i < answers.size(); i++) { out.println(answers.get(i)); }
		out.close();
	}
 
	public static class UnionFind {
		int[] nodes;
		int[] sizes;
		int components;
 
		UnionFind(int n) {
			nodes = new int[n];
			sizes = new int[n];
			components = n;
			for (int i = 0; i < n; i++) {
				nodes[i] = i;
				sizes[i] = 1;
			}
		}
 
		void union(int p, int q) {
			int i = root(p);
			int j = root(q);
			if (i == j) return;
 
			components--;
			if (sizes[i] < sizes[j]) {
				nodes[i] = nodes[j];
				sizes[j] += sizes[i];
			} else {
				nodes[j] = nodes[i];
				sizes[i] += sizes[j];
			}
		}
 
		int root(int index) {
			while (nodes[index] != index) {
				nodes[index] = nodes[nodes[index]];
				index = nodes[index];
			}
			return index;
		}
 
		boolean connected(int p, int q) { return root(p) == root(q); }
	}
}