### [A. Graph: Road Trip](https://mirror.codeforces.com/group/e8jUNwDnHj/contest/500552/problem/A)↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
test_count = read()↵
for test in range(test_count):↵
n, m = read_list();↵
↵
g = [[] for i in range(n+1)]↵
mark = [False] * (n+1)↵
↵
for i in range(m):↵
u, v = read_list()↵
g[u].append(v)↵
g[v].append(u)↵
↵
def dfs(node):↵
if mark[node]:↵
return↵
mark[node] = True↵
for i in g[node]:↵
dfs(i)↵
↵
↵
dfs(1)↵
↵
if mark[n]:↵
print("yes")↵
else:↵
print("no")↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="C++ Solution">↵
```c++↵
#include "cstdlib"↵
#include "cstring"↵
#include "cmath"↵
#include "iostream"↵
#include "stack"↵
#include "vector"↵
#include "array"↵
#include "queue"↵
#include "algorithm"↵
#include "map"↵
#include "set"↵
#include "unordered_map"↵
#include "unordered_set"↵
#include "numeric"↵
#include "string"↵
#include "iomanip"↵
#include "climits"↵
#include "functional"↵
#include "cctype"↵
↵
using namespace std; ↵
#define array_size(a) (sizeof(a)/sizeof(a[0]))↵
#define rep(name, start, end) for (int name=(start); name<=(end); name++)↵
#define repr(name, start, end) for (int name=(start); name>=(end); name--)↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
using ull = unsigned long long;↵
using uint = unsigned int;↵
#define MOD 1000000007↵
// #define MOD 998244353↵
#define NL '\n'↵
#define nl '\n'↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
template<typename T> ↵
using max_heap = priority_queue<T>;↵
↵
template<typename T> ↵
using matrix = vector<vector<T>>;↵
↵
template<typename T> ↵
void _dbg(const char* name, T cont) {↵
cerr << "#" << name << " = {"; ↵
int n = cont.size();↵
int idx = 0;↵
for (auto i: cont) {↵
cerr << i;↵
if (++idx < n) {↵
cerr << ", ";↵
}↵
}↵
cerr << "}" << nl;↵
}↵
↵
↵
#ifndef ONLINE_JUDGE↵
#define dbg(x) _dbg(#x, x) ↵
#else ↵
#define dbg(x)↵
#endif↵
↵
matrix<int> g;↵
vector<bool> v;↵
↵
void dfs(int node) {↵
if (v[node]) return;↵
v[node] = true;↵
for (int i: g[node]) {↵
dfs(i);↵
}↵
}↵
↵
void solve() {↵
int n, m; cin >> n >> m;↵
g.resize(n+1);↵
v.resize(n+1);↵
rep (i, 1, m) {↵
int a, b; cin >> a >> b;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
dfs(1);↵
if (v[n]) {↵
cout << "YES" << nl;↵
} else {↵
cout << "NO" << nl;↵
}↵
g.clear();↵
v.clear();↵
} ↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
↵
int t=1;↵
cin >> t;↵
rep(test, 1, t) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
### [B. Graph: Counting Islands](https://mirror.codeforces.com/group/e8jUNwDnHj/contest/500552/problem/B)↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
test_count = read()↵
for test in range(test_count):↵
n, m = read_list();↵
↵
g = [[] for i in range(n+1)]↵
mark = [False] * (n+1)↵
↵
for i in range(m):↵
u, v = read_list()↵
g[u].append(v)↵
g[v].append(u)↵
↵
def dfs(node):↵
if mark[node]:↵
return↵
mark[node] = True↵
for i in g[node]:↵
dfs(i)↵
↵
result = 0↵
for i in range(1, n+1):↵
if not mark[i]:↵
dfs(i)↵
result += 1↵
print(result)↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="C++ Solution">↵
```c++↵
#include "cstdlib"↵
#include "cstring"↵
#include "cmath"↵
#include "iostream"↵
#include "stack"↵
#include "vector"↵
#include "array"↵
#include "queue"↵
#include "algorithm"↵
#include "map"↵
#include "set"↵
#include "unordered_map"↵
#include "unordered_set"↵
#include "numeric"↵
#include "string"↵
#include "iomanip"↵
#include "climits"↵
#include "functional"↵
#include "cctype"↵
↵
using namespace std; ↵
#define array_size(a) (sizeof(a)/sizeof(a[0]))↵
#define rep(name, start, end) for (int name=(start); name<=(end); name++)↵
#define repr(name, start, end) for (int name=(start); name>=(end); name--)↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
using ull = unsigned long long;↵
using uint = unsigned int;↵
#define MOD 1000000007↵
// #define MOD 998244353↵
#define NL '\n'↵
#define nl '\n'↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
template<typename T> ↵
using max_heap = priority_queue<T>;↵
↵
template<typename T> ↵
using matrix = vector<vector<T>>;↵
↵
template<typename T> ↵
void _dbg(const char* name, T cont) {↵
cerr << "#" << name << " = {"; ↵
int n = cont.size();↵
int idx = 0;↵
for (auto i: cont) {↵
cerr << i;↵
if (++idx < n) {↵
cerr << ", ";↵
}↵
}↵
cerr << "}" << nl;↵
}↵
↵
↵
#ifndef ONLINE_JUDGE↵
#define dbg(x) _dbg(#x, x) ↵
#else ↵
#define dbg(x)↵
#endif↵
↵
matrix<int> g;↵
vector<bool> v;↵
↵
void dfs(int node) {↵
if (v[node]) return;↵
v[node] = true;↵
for (int i: g[node]) {↵
dfs(i);↵
}↵
}↵
↵
void solve() {↵
int n, m; cin >> n >> m;↵
g.resize(n+1);↵
v.resize(n+1);↵
rep (i, 1, m) {↵
int a, b; cin >> a >> b;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
int result = 0;↵
rep (i, 1, n) {↵
if (!v[i]) {↵
dfs(i);↵
result++;↵
}↵
}↵
cout << result << nl;↵
g.clear();↵
v.clear();↵
} ↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
↵
int t=1;↵
cin >> t;↵
rep(test, 1, t) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
### [C. Graph: Counting Rooms](https://mirror.codeforces.com/group/e8jUNwDnHj/contest/500552/problem/C)↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
test_count = read()↵
for test in range(test_count):↵
n, m = read_list();↵
↵
g = [input() for i in range(n)]↵
mark = [[False] * m for i in range(n)]↵
↵
def dfs(i, j):↵
if g[i][j] == '#' or mark[i][j]:↵
return↵
mark[i][j] = True↵
dfs(i+1, j)↵
dfs(i-1, j)↵
dfs(i, j+1)↵
dfs(i, j-1)↵
↵
result = 0↵
for i in range(n):↵
for j in range(m):↵
if not mark[i][j] and g[i][j] == '.':↵
dfs(i, j)↵
result += 1↵
print(result)↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="C++ Solution">↵
```c++↵
#include "cstdlib"↵
#include "cstring"↵
#include "cmath"↵
#include "iostream"↵
#include "stack"↵
#include "vector"↵
#include "array"↵
#include "queue"↵
#include "algorithm"↵
#include "map"↵
#include "set"↵
#include "unordered_map"↵
#include "unordered_set"↵
#include "numeric"↵
#include "string"↵
#include "iomanip"↵
#include "climits"↵
#include "functional"↵
#include "cctype"↵
↵
using namespace std; ↵
#define array_size(a) (sizeof(a)/sizeof(a[0]))↵
#define rep(name, start, end) for (int name=(start); name<=(end); name++)↵
#define repr(name, start, end) for (int name=(start); name>=(end); name--)↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
using ull = unsigned long long;↵
using uint = unsigned int;↵
#define MOD 1000000007↵
// #define MOD 998244353↵
#define NL '\n'↵
#define nl '\n'↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
template<typename T> ↵
using max_heap = priority_queue<T>;↵
↵
template<typename T> ↵
using matrix = vector<vector<T>>;↵
↵
template<typename T> ↵
void _dbg(const char* name, T cont) {↵
cerr << "#" << name << " = {"; ↵
int n = cont.size();↵
int idx = 0;↵
for (auto i: cont) {↵
cerr << i;↵
if (++idx < n) {↵
cerr << ", ";↵
}↵
}↵
cerr << "}" << nl;↵
}↵
↵
↵
#ifndef ONLINE_JUDGE↵
#define dbg(x) _dbg(#x, x) ↵
#else ↵
#define dbg(x)↵
#endif↵
↵
vector<string> g;↵
vector<vector<bool>> v;↵
↵
void dfs(int i, int j) {↵
if (g[i][j] == '#' || v[i][j]) return;↵
v[i][j] = true;↵
↵
dfs(i,j+1);↵
dfs(i,j-1);↵
dfs(i+1,j);↵
dfs(i-1,j);↵
}↵
↵
void solve() {↵
int n, m; cin >> n >> m;↵
g.resize(n);↵
v.resize(n, vector<bool>(m));↵
rep (i, 0, n-1) {↵
cin >> g[i];↵
}↵
int result = 0;↵
rep (i, 0, n-1) {↵
rep (j, 0, m-1) {↵
if (!v[i][j] && g[i][j] == '.') {↵
dfs(i, j);↵
result++;↵
}↵
}↵
}↵
cout << result << nl;↵
g.clear();↵
v.clear();↵
} ↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
↵
int t=1;↵
cin >> t;↵
rep(test, 1, t) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
test_count = read()↵
for test in range(test_count):↵
n, m = read_list();↵
↵
g = [[] for i in range(n+1)]↵
mark = [False] * (n+1)↵
↵
for i in range(m):↵
u, v = read_list()↵
g[u].append(v)↵
g[v].append(u)↵
↵
def dfs(node):↵
if mark[node]:↵
return↵
mark[node] = True↵
for i in g[node]:↵
dfs(i)↵
↵
↵
dfs(1)↵
↵
if mark[n]:↵
print("yes")↵
else:↵
print("no")↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="C++ Solution">↵
```c++↵
#include "cstdlib"↵
#include "cstring"↵
#include "cmath"↵
#include "iostream"↵
#include "stack"↵
#include "vector"↵
#include "array"↵
#include "queue"↵
#include "algorithm"↵
#include "map"↵
#include "set"↵
#include "unordered_map"↵
#include "unordered_set"↵
#include "numeric"↵
#include "string"↵
#include "iomanip"↵
#include "climits"↵
#include "functional"↵
#include "cctype"↵
↵
using namespace std; ↵
#define array_size(a) (sizeof(a)/sizeof(a[0]))↵
#define rep(name, start, end) for (int name=(start); name<=(end); name++)↵
#define repr(name, start, end) for (int name=(start); name>=(end); name--)↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
using ull = unsigned long long;↵
using uint = unsigned int;↵
#define MOD 1000000007↵
// #define MOD 998244353↵
#define NL '\n'↵
#define nl '\n'↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
template<typename T> ↵
using max_heap = priority_queue<T>;↵
↵
template<typename T> ↵
using matrix = vector<vector<T>>;↵
↵
template<typename T> ↵
void _dbg(const char* name, T cont) {↵
cerr << "#" << name << " = {"; ↵
int n = cont.size();↵
int idx = 0;↵
for (auto i: cont) {↵
cerr << i;↵
if (++idx < n) {↵
cerr << ", ";↵
}↵
}↵
cerr << "}" << nl;↵
}↵
↵
↵
#ifndef ONLINE_JUDGE↵
#define dbg(x) _dbg(#x, x) ↵
#else ↵
#define dbg(x)↵
#endif↵
↵
matrix<int> g;↵
vector<bool> v;↵
↵
void dfs(int node) {↵
if (v[node]) return;↵
v[node] = true;↵
for (int i: g[node]) {↵
dfs(i);↵
}↵
}↵
↵
void solve() {↵
int n, m; cin >> n >> m;↵
g.resize(n+1);↵
v.resize(n+1);↵
rep (i, 1, m) {↵
int a, b; cin >> a >> b;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
dfs(1);↵
if (v[n]) {↵
cout << "YES" << nl;↵
} else {↵
cout << "NO" << nl;↵
}↵
g.clear();↵
v.clear();↵
} ↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
↵
int t=1;↵
cin >> t;↵
rep(test, 1, t) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
### [B. Graph: Counting Islands](https://mirror.codeforces.com/group/e8jUNwDnHj/contest/500552/problem/B)↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
test_count = read()↵
for test in range(test_count):↵
n, m = read_list();↵
↵
g = [[] for i in range(n+1)]↵
mark = [False] * (n+1)↵
↵
for i in range(m):↵
u, v = read_list()↵
g[u].append(v)↵
g[v].append(u)↵
↵
def dfs(node):↵
if mark[node]:↵
return↵
mark[node] = True↵
for i in g[node]:↵
dfs(i)↵
↵
result = 0↵
for i in range(1, n+1):↵
if not mark[i]:↵
dfs(i)↵
result += 1↵
print(result)↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="C++ Solution">↵
```c++↵
#include "cstdlib"↵
#include "cstring"↵
#include "cmath"↵
#include "iostream"↵
#include "stack"↵
#include "vector"↵
#include "array"↵
#include "queue"↵
#include "algorithm"↵
#include "map"↵
#include "set"↵
#include "unordered_map"↵
#include "unordered_set"↵
#include "numeric"↵
#include "string"↵
#include "iomanip"↵
#include "climits"↵
#include "functional"↵
#include "cctype"↵
↵
using namespace std; ↵
#define array_size(a) (sizeof(a)/sizeof(a[0]))↵
#define rep(name, start, end) for (int name=(start); name<=(end); name++)↵
#define repr(name, start, end) for (int name=(start); name>=(end); name--)↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
using ull = unsigned long long;↵
using uint = unsigned int;↵
#define MOD 1000000007↵
// #define MOD 998244353↵
#define NL '\n'↵
#define nl '\n'↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
template<typename T> ↵
using max_heap = priority_queue<T>;↵
↵
template<typename T> ↵
using matrix = vector<vector<T>>;↵
↵
template<typename T> ↵
void _dbg(const char* name, T cont) {↵
cerr << "#" << name << " = {"; ↵
int n = cont.size();↵
int idx = 0;↵
for (auto i: cont) {↵
cerr << i;↵
if (++idx < n) {↵
cerr << ", ";↵
}↵
}↵
cerr << "}" << nl;↵
}↵
↵
↵
#ifndef ONLINE_JUDGE↵
#define dbg(x) _dbg(#x, x) ↵
#else ↵
#define dbg(x)↵
#endif↵
↵
matrix<int> g;↵
vector<bool> v;↵
↵
void dfs(int node) {↵
if (v[node]) return;↵
v[node] = true;↵
for (int i: g[node]) {↵
dfs(i);↵
}↵
}↵
↵
void solve() {↵
int n, m; cin >> n >> m;↵
g.resize(n+1);↵
v.resize(n+1);↵
rep (i, 1, m) {↵
int a, b; cin >> a >> b;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
int result = 0;↵
rep (i, 1, n) {↵
if (!v[i]) {↵
dfs(i);↵
result++;↵
}↵
}↵
cout << result << nl;↵
g.clear();↵
v.clear();↵
} ↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
↵
int t=1;↵
cin >> t;↵
rep(test, 1, t) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
### [C. Graph: Counting Rooms](https://mirror.codeforces.com/group/e8jUNwDnHj/contest/500552/problem/C)↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
test_count = read()↵
for test in range(test_count):↵
n, m = read_list();↵
↵
g = [input() for i in range(n)]↵
mark = [[False] * m for i in range(n)]↵
↵
def dfs(i, j):↵
if g[i][j] == '#' or mark[i][j]:↵
return↵
mark[i][j] = True↵
dfs(i+1, j)↵
dfs(i-1, j)↵
dfs(i, j+1)↵
dfs(i, j-1)↵
↵
result = 0↵
for i in range(n):↵
for j in range(m):↵
if not mark[i][j] and g[i][j] == '.':↵
dfs(i, j)↵
result += 1↵
print(result)↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="C++ Solution">↵
```c++↵
#include "cstdlib"↵
#include "cstring"↵
#include "cmath"↵
#include "iostream"↵
#include "stack"↵
#include "vector"↵
#include "array"↵
#include "queue"↵
#include "algorithm"↵
#include "map"↵
#include "set"↵
#include "unordered_map"↵
#include "unordered_set"↵
#include "numeric"↵
#include "string"↵
#include "iomanip"↵
#include "climits"↵
#include "functional"↵
#include "cctype"↵
↵
using namespace std; ↵
#define array_size(a) (sizeof(a)/sizeof(a[0]))↵
#define rep(name, start, end) for (int name=(start); name<=(end); name++)↵
#define repr(name, start, end) for (int name=(start); name>=(end); name--)↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
using ull = unsigned long long;↵
using uint = unsigned int;↵
#define MOD 1000000007↵
// #define MOD 998244353↵
#define NL '\n'↵
#define nl '\n'↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
template<typename T> ↵
using max_heap = priority_queue<T>;↵
↵
template<typename T> ↵
using matrix = vector<vector<T>>;↵
↵
template<typename T> ↵
void _dbg(const char* name, T cont) {↵
cerr << "#" << name << " = {"; ↵
int n = cont.size();↵
int idx = 0;↵
for (auto i: cont) {↵
cerr << i;↵
if (++idx < n) {↵
cerr << ", ";↵
}↵
}↵
cerr << "}" << nl;↵
}↵
↵
↵
#ifndef ONLINE_JUDGE↵
#define dbg(x) _dbg(#x, x) ↵
#else ↵
#define dbg(x)↵
#endif↵
↵
vector<string> g;↵
vector<vector<bool>> v;↵
↵
void dfs(int i, int j) {↵
if (g[i][j] == '#' || v[i][j]) return;↵
v[i][j] = true;↵
↵
dfs(i,j+1);↵
dfs(i,j-1);↵
dfs(i+1,j);↵
dfs(i-1,j);↵
}↵
↵
void solve() {↵
int n, m; cin >> n >> m;↵
g.resize(n);↵
v.resize(n, vector<bool>(m));↵
rep (i, 0, n-1) {↵
cin >> g[i];↵
}↵
int result = 0;↵
rep (i, 0, n-1) {↵
rep (j, 0, m-1) {↵
if (!v[i][j] && g[i][j] == '.') {↵
dfs(i, j);↵
result++;↵
}↵
}↵
}↵
cout << result << nl;↵
g.clear();↵
v.clear();↵
} ↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
↵
int t=1;↵
cin >> t;↵
rep(test, 1, t) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
