1. Drgee sum ============

• 2*(degree counter)
• Coming soon....

2.handshaking lemma ===================

• even node always get odd number of degree

1. In degree and out degree

• sum of indegree = sum of outdegree

1. Calculating Complexity of graph

• V = vertex , E = edges
• O(V+E) or O(V^2)

1. How to store Graph ---------------------

• Coming soon...

1. 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";

}

1. 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'; 

*/

}

1. 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; 

    } 

}

}

1. CONNECTED COMPONETED

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;

}

1. 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; 

        } 

    } 

}

}

1. 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;

}

1. 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";

}

Coming soon.... -