#include<bits/stdc++.h>
using namespace std;
class graph
{
int v;
list<int> *adj;
public:
graph(int v)
{
this->v=v;
adj=new list<int>[v];
}
void add_edge(int v,int w)
{
adj[v].push_back(w);
}
void dfs(int start,bool visited[]);
int find_mother();
};
void graph::dfs(int start,bool visited[])
{
visited[start]=true;
for(auto itr=adj[start].begin();itr!=adj[start].end();itr++)
{
if(!visited[*itr])
{
dfs(*itr,visited);
}
}
}
int graph::find_mother()
{
bool *visited=new bool[v];
for(int i=0;i<v;i++)
visited[i]=false;
int m=0;
for(int i=0;i<v;i++)
{
if(visited[i]==false)
{
dfs(i,visited);
m=i;
}
}
for(int i=0;i<v;i++)
visited[i]=false;
dfs(m,visited);
for(int i=0;i<v;i++)
{
if(visited[i]==false)
return -1;
}
return m;
}
int main()
{
graph g(5);
g.add_edge(0,1);
g.add_edge(0,2);
g.add_edge(1,2);
g.add_edge(2,3);
g.add_edge(2,0);
cout<<g.find_mother()<<endl;
return 0;
}
using namespace std;
class graph
{
int v;
list<int> *adj;
public:
graph(int v)
{
this->v=v;
adj=new list<int>[v];
}
void add_edge(int v,int w)
{
adj[v].push_back(w);
}
void dfs(int start,bool visited[]);
int find_mother();
};
void graph::dfs(int start,bool visited[])
{
visited[start]=true;
for(auto itr=adj[start].begin();itr!=adj[start].end();itr++)
{
if(!visited[*itr])
{
dfs(*itr,visited);
}
}
}
int graph::find_mother()
{
bool *visited=new bool[v];
for(int i=0;i<v;i++)
visited[i]=false;
int m=0;
for(int i=0;i<v;i++)
{
if(visited[i]==false)
{
dfs(i,visited);
m=i;
}
}
for(int i=0;i<v;i++)
visited[i]=false;
dfs(m,visited);
for(int i=0;i<v;i++)
{
if(visited[i]==false)
return -1;
}
return m;
}
int main()
{
graph g(5);
g.add_edge(0,1);
g.add_edge(0,2);
g.add_edge(1,2);
g.add_edge(2,3);
g.add_edge(2,0);
cout<<g.find_mother()<<endl;
return 0;
}
Comments
Post a Comment