- 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
- Calculating Complexity of graph
- V = vertex , E = edges
- O(V+E) or O(V^2)
- How to store Graph ---------------------
- Coming soon...
- 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";}
- 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';
*/}
- 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;
}
}}
- 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;}
- 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;
}
}
}}
- 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";}
