---
Basic Graph Theory Short Note
1. Degree Sum
[2 \times (\text{degree counter})]
2. Handshaking Lemma
Even nodes always have an odd number of degrees. In-degree and out-degree satisfy: [ \text{Sum of in-degree} = \text{Sum of out-degree} ]
3. Calculating the Complexity of Graph
[ V = \text{vertices}, E = \text{edges} ] [ \mathcal{O}(V + E) \text{ or } \mathcal{O}(V^2) ]
4. How to Store Graph
Coming soon...
5. Adjacency Matrix
#include<bits/stdc++.h>
using namespace std;
int g[100][100];
int main() {
int n, e; cin >> n >> e;
while(e--) {
int u, v; cin >> u >> v;
g[u][v] = 1;
g[v][u] = 1;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
if(g[4][2]) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
6. Adjacency List
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
vector<int> g[N];
int indgr[N], outdgr[N];
int main() {
int n, e; cin >> n >> e;
while(e--) {
int u, v; cin >> u >> v;
indgr[v]++;
outdgr[u]++;
g[u].push_back(v);
}
for(int i = 0; i <= n; i++) {
cout << indgr[i] << " ";
}
cout << "\n";
for(int i = 0; i <= n; i++) {
cout << outdgr[i] << " ";
}
}
7. DFS
#include<bits/stdc++.h>
#define itsmdshahin ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
const int N = 1e5 + 9;
bool vis[N];
vector<int> g[N];
void dfs(int s) {
vis[s] = true;
for(auto it : g[s]) {
if(!vis[it]) {
cout << "VISITED " << it << endl;
dfs(it);
}
}
}
int main() {
int n, m; cin >> n >> m;
while(m--) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int s; cin >> s;
dfs(s);
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
cout << "DISCONNECTED GRAPH\n";
return 0;
}
}
}
8. Connected Components
#include<bits/stdc++.h>
#define itsmdshahin ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
const int N = 1e5 + 9;
bool vis[N];
vector<int> g[N];
void dfs(int s) {
vis[s] = true;
for(auto it : g[s]) {
if(!vis[it]) {
dfs(it);
}
}
}
int main() {
int n, m; cin >> n >> m;
while(m--) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
dfs(i);
++ans;
}
}
cout << "Connected Components: " << ans << endl;
}
9. BFS Implementation
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> G[N];
bool Vis[N];
int main() {
int n, e; cin >> n >> e;
while(e--) {
int x, y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
queue<int> q;
q.push(1);
Vis[1] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto it : G[u]) {
if(!Vis[it]) {
q.push(it);
Vis[v] = true;
}
}
}
}
10. BFS Component Find in Graph
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> G[N];
bool Vis[N];
queue<int> q;
void bfs(int n) {
q.push(n);
Vis[n] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto it : G[u]) {
if(!Vis[it]) {
q.push(it);
Vis[it] = true;
}
}
}
}
int main() {
int n, e; cin >> n >> e;
int ans = 0;
for(int i = 0; i < n; i++) {
if(!Vis[i]) {
bfs(i);
++ans;
}
}
cout << ans << endl;
}
11. BFS Distance Find in Graph Theory
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> G[N];
bool Vis[N];
vector<int> dis(N);
int main() {
int n, e; cin >> n >> e;
queue<int> q;
q.push(1);
Vis[1] = true;
dis[1] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto it : G[u]) {
if(!Vis[it]) {
q.push(it);
dis[it] = dis[u] + 1;
Vis[it] = true;
}
}
}
for(int i = 1; i <= n; i++) {
cout << dis[i] << " ";
}
cout << endl;
}
---
12. BFS Path Find in Graph Theory
// Implementation will be added soon...
13. Bicoloring and Bipartite Graph
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
vector<int> g[N];
bool vis[N], col[N], ok;
void dfs(int u) {
vis[u] = true;
for(auto v : g[u]) {
if(!vis[v]) {
col[v] = col[u] ^ 1;
dfs(v);
} else {
if(col[u] == col[v]) ok = false;
}
}
}
int main() {
int n, e;
cin >> n >> e;
while(e--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ok = true;
for(int i = 1; i <= n; i++) {
if(!vis[i]) dfs(i);
}
if(ok) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
14. Articulation Points and Bridges
// Implementation will be added soon...
15. Topological Sorting
// Implementation will be added soon...
16. Dijkstra's Algorithm
// Implementation will be added soon...
17. Bellman-Ford Algorithm
// Implementation will be added soon...
18. Floyd-Warshall Algorithm
// Implementation will be added soon...
19. Minimum Spanning Tree (Prim's Algorithm)
// Implementation will be added soon...
20. Minimum Spanning Tree (Kruskal's Algorithm)
// Implementation will be added soon...
