A. Graph: Road Trip
Python Solution
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")
C++ Solution
#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();
}
}
B. Graph: Counting Islands
Python Solution
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)
C++ Solution
#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();
}
}
C. Graph: Counting Rooms
Python Solution
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)
C++ Solution
#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();
}
}
Auto comment: topic has been updated by ammar007 (previous revision, new revision, compare).