code. compile. run. debug. share.
Source Code
Language
#include<bits/stdc++.h>
using namespace std;
template<typename T>
class graph{
map<T,list<T>>g;
public:
int fact(int n)
{
if(n<=1)
{
return 1;
}
return fact(n-1)*n;
}
int ncr(int n,int r)
{
return fact(n)/(fact(n-r)*fact(r));
}
void addedge(int x,int y)
{
g[x].push_back(y);
g[y].push_back(x);
}
int dfs_helper(T node,map<T,bool>&visited)
{
visited[node]=true;
int count=0;
for(auto nbr:g[node])
{
if(!visited[nbr])
{
count++;
dfs_helper(nbr,visited);
}
}
return count;
}
void dfs(int n)
{
map<T,bool>visited;
for(auto p:g)
{
T node=p.first;
visited[node]=false;
}
for(auto p:g)
{
T node=p.first;
int count=0;
int ans=ncr(n,2);
if(!visited[node])
{
count=dfs_helper(node,visited);
ans-=ncr(count,2);
}
}
}
};
int main()
{
int n=5;
graph<int>gr;
gr.addedge(5,3);
gr.addedge(0,1);
gr.addedge(2,3);
gr.addedge(0,4);
gr.dfs(n);
}
#include<bits/stdc++.h>
using namespace std;
template<typename T>
class graph{
map<T,list<T>>g;
public:
int count;
int fact(int n)
{
if(n<=1)
{
return 1;
}
return fact(n-1)*n;
}
int ncr(int n,int r)
{
return fact(n)/(fact(n-r)*fact(r));
}
void addedge(int x,int y)
{
g[x].push_back(y);
g[y].push_back(x);
}
int dfs_helper(T node,map<T,bool>&visited)
{
visited[node]=true;
for(auto nbr:g[node])
{
if(!visited[nbr])
{
count++;
dfs_helper(nbr,visited);
}
}
return count;
}
void dfs(int n)
{
map<T,bool>visited;
for(auto p:g)
{
T node=p.first;
visited[node]=false;
}
int c,ans;
for(auto p:g)
{
T node=p.first;
ans=ncr(n,2);
count=0;
if(!visited[node])
{
c=dfs_helper(node,visited);
cout<<c<<"\n";
ans-=ncr(c,2);
}
}
cout<<ans;
}
};
int main()
{
int n=5;
graph<int>gr;
gr.addedge(5,3);
gr.addedge(0,1);
gr.addedge(2,3);
gr.addedge(0,4);
gr.dfs(n);
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|