1. Drgee sum
- 2*(degree counter)
- Coming soon....
2. Handshaking lemma
- even node always get odd number of degree
- In-degree and out-degree
- Sum of indegree = sum of outdegree
4. Calculating the Complexity of Graph
- V = vertex , E = edges
- O(V+E) or O(V^2)
5. How to store Graph
- Coming soon...
6. 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; //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 g[N]; int indgr[N],outdgr[N]; int main() { int n,e;cin >>n>>e; while(e--){ int u,v; cin >> u >> v; // finding indgree and outdgree for array
indgr[v]++; outdgr[u]++; g[u].push_back(v);
//g[v].push_back(u);
}
/* // find the list
for(auto it:g[2]){
cout << it << " ";
}
*/
// finding indgree loop
for(int i=0;i<=n;i++){
cout << indgr[i] <<" ";
}
cout << "\n";
// finding outdegree loop
for(int i=0;i<=n;i++){
cout << outdgr[i] <<" ";
}
// finding the dgree using adjcenncy list
/*
for(int i=0;i<=n;i++){
cout << g[i].size() <<" ";
}
cout << '\n';
*/}
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 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 << "DISCONNETED GRAPH\n"; return 0; } } }
8. CONNECTED COMPONENT
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 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,s;cin>>s; int ans=0;
for(int i=1;i<=n;i++){ if(!vis[i]){ dfs(i); ++ans; } } cout << "Connected Compoments: " << ans << endl; }
9. BFS implement
include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
vector 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 Graph?
include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
vector G[N];
bool Vis[N];
queue 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;
while(e--){
int x,y;cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
int ans=0;
for(int i=0;i<n;i++){
if(!Vis[i]){
bfs(i);
++ans;
}
}
cout << ans << endl;}
- BFS Distance find Graph Theory?
include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
vector G[N];
bool Vis[N];
vector dis(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;
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 Graph Theory? ------------------------------
Coming soon....
13 Bicoloring and Bipartite Graph ---------------------------------
include<bits/stdc++.h>
using namespace std;
const int N = 105;
vector g[N];
int indgr[N],outdgr[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";}
