Pagini recente » Cod sursa (job #2966542) | Cod sursa (job #2075239) | Cod sursa (job #2370648) | Cod sursa (job #961665) | Cod sursa (job #2791232)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
class Graph{
private:
int n;
vector < vector<int> > la;
vector<vector<int>> componente_biconexe;
vector<int> lowest, level, father;
stack<pair<int,int>> edges_biconexe;
int nr_comp_biconexe;
void dfs(int nod_crt, vector<bool> &viz);
void dfs_biconexe(int nod_crt);
public:
Graph(int nr_noduri):n(nr_noduri), la(nr_noduri+1), lowest(0), level(0), father(0), nr_comp_biconexe(0), componente_biconexe(0){}
~Graph() = default;
void add_edge(int from, int to){
la[from].push_back(to);
}
void bfs_print_dist(int start); // Starting from node 1
int nr_conexe_dfs();
void print_sortare_topologica(ostream &out);
void print_comp_biconexe_udg(ostream &out);
};
void Graph::bfs_print_dist(int start)
{
vector<int> dist(n+1,0);
queue<int> q;
int nod_crt;
q.push(start);
dist[start]=1;
while(!q.empty())
{
nod_crt = q.front();
q.pop();
for(auto nod_vecin: la[nod_crt])
{
if(dist[nod_vecin] == 0)
{
dist[nod_vecin] = dist[nod_crt] + 1;
q.push(nod_vecin);
}
}
}
for(int i=1;i<=n;++i)
g<<dist[i]-1<<' ';
}
int Graph::nr_conexe_dfs()
{
vector<bool> viz(n+1, false);
int nr_c=0;
for(int i=1;i<=n;++i)
{
if(!viz[i])
{
++nr_c;
dfs(i, viz);
}
}
return nr_c;
}
void Graph::print_sortare_topologica(ostream &out)
{
queue<int> zero_nodes;
int grades[n+1] = {0}, i;
int nod_curent;
for(i=1;i<=n;++i)
{
for(auto nod_vecin: la[i])
++grades[nod_vecin];
}
for(i=1; i<=n;++i)
if(grades[i] == 0)
zero_nodes.push(i);
if(zero_nodes.empty())
{
cout<<"Cyclic Graph. Can't sort.";
return;
}
while(!zero_nodes.empty())
{
nod_curent = zero_nodes.front();
zero_nodes.pop();
out<<nod_curent<<' ';
for(auto nod_vecin: la[nod_curent])
{
--grades[nod_vecin];
if(grades[nod_vecin] == 0)
zero_nodes.push(nod_vecin);
}
}
}
void Graph::dfs(int nod_crt, vector<bool> &viz)
{
for(auto nod_vecin: la[nod_crt])
{
if(!viz[nod_vecin])
{
viz[nod_vecin] = true;
dfs(nod_vecin, viz);
}
}
}
void Graph::dfs_biconexe(int nod_crt)
{
level[nod_crt] = level[father[nod_crt]] + 1;
lowest[nod_crt] = level[nod_crt];
for(auto nod_vecin: la[nod_crt])
{
if(level[nod_vecin] == 0)
{
father[nod_vecin] = nod_crt;
edges_biconexe.push(make_pair(nod_crt, nod_vecin));
dfs_biconexe(nod_vecin);
if(lowest[nod_vecin] >= level[nod_crt])
{
int a,b;
++nr_comp_biconexe;
vector<int> componenta_biconexa;
do
{
a=edges_biconexe.top().first;
b=edges_biconexe.top().second;
edges_biconexe.pop();
componenta_biconexa.push_back(a);
componenta_biconexa.push_back(b);
}while(a!=nod_crt && b!=nod_vecin && !edges_biconexe.empty());
sort(componenta_biconexa.begin(), componenta_biconexa.end());
componente_biconexe.push_back(componenta_biconexa);
}
else
lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
}
else if(nod_vecin!= father[nod_crt])
lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);;
}
}
void Graph::print_comp_biconexe_udg(ostream &out)
{
lowest.resize(n+1, 0);
level.resize(n+1, 0);
father.resize(n+1, 0);
dfs_biconexe(1);
out<<nr_comp_biconexe<<'\n';
for(auto x:componente_biconexe)
{
out<<x[0];
for(int i=1;i<x.size();++i)
if(x[i]!=x[i-1])
out<<' '<<x[i];
out<<'\n';
}
}
int main()
{
int n,m;
int a,b;
f>>n>>m;
Graph gr(n);
for(int i=0;i<m;++i)
{
f>>a>>b;
gr.add_edge(a,b);
gr.add_edge(b,a);
}
f.close();
gr.print_comp_biconexe_udg(g);
g.close();
return 0;
}