Pagini recente » Cod sursa (job #3148743) | Istoria paginii utilizator/bibilush | Cod sursa (job #202350) | Cod sursa (job #960040) | Cod sursa (job #476579)
Cod sursa(job #476579)
#ifndef _ALGORITHM_H
#define _ALGORITHM_H
#include <fstream>
using namespace std;
/**
Algorithm abstract class
specifies protocol
*/
template<class I, class O>
class Algorithm
{
protected:
I ∈
O &out;
/**
algorithm method
instantiates i/o
*/
Algorithm(I &, O &);
};
/**
algorithm method
instantiates i/o
*/
template<class I, class O>
Algorithm<I, O>::Algorithm(I &inp, O &outp): in(inp), out(outp)
{
}
#endif
#ifndef _BICONNECTIVITY_H
#define _BICONNECTIVITY_H
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
/**
Biconnectivity class
solves the connectivity in a graph problem
*/
class Biconnectivity: public Algorithm< vector<int>, pair< vector<int>, vector< set<int> > > >
{
int N, T, S;
vector<int> Dfn, Low;
vector< vector<int> > Deg;
stack< pair<int, int> > Stk;
public:
/**
biconnectivity method
runs algorithm
*/
Biconnectivity(vector<int> &, pair< vector<int>, vector< set<int> > > &);
private:
/**
read method
reads input
*/
void Read();
/**
solve method
solves problem
*/
void Solve();
/**
bidfs method
computes biconnectivity
*/
void BiDFS(int, int);
};
#endif
/**
biconnectivity method
runs algorithm
*/
Biconnectivity::Biconnectivity(vector<int> &in, pair< vector<int>, vector< set<int> > > &out):
Algorithm< vector<int>, pair< vector<int>, vector< set<int> > > >(in, out), N(0), S(0), T(0)
{
Read();
Solve();
}
/**
read method
reads input
*/
void Biconnectivity::Read()
{
int x, y, c, m;
vector<int> Aux1;
N = in[0];
m = in[1];
for (c = 0; c <= N; ++c)
{
Deg.push_back(Aux1);
}
for (c = 0; c < m; ++c)
{
x = in[c * 2 + 2];
y = in[c * 2 + 3];
Deg[x].push_back(y);
Deg[y].push_back(x);
}
}
/**
solve method
solves problem
*/
void Biconnectivity::Solve()
{
Dfn.assign(N + 1, 0);
Low.assign(N + 1, 0);
Stk.push(pair<int, int>(-1, 1));
BiDFS(1, -1);
if (S >= 2)
{
out.first.push_back(1);
}
}
/**
bidfs method
computes biconnectivity
*/
void Biconnectivity::BiDFS(int u, int t)
{
int v;
Dfn[u] = Low[u] = ++T;
for (vector<int>::iterator i = Deg[u].begin(); i != Deg[u].end(); ++i)
{
v = *i;
if (v != t && Dfn[v] < Dfn[u])
{
Stk.push(pair<int, int>(u, v));
}
if (!Dfn[v])
{
if (u == 1)
{
++S;
}
BiDFS(v, u);
Low[u] = min(Low[u], Low[v]);
if (Dfn[u] <= Low[v])
{
if (u != 1)
{
out.first.push_back(u);
}
pair<int, int> p;
out.second.push_back(set<int>());
do
{
p = Stk.top();
out.second[out.second.size() - 1].insert(p.first);
out.second[out.second.size() - 1].insert(p.second);
Stk.pop();
}
while(p.first != u || p.second != v);
}
}
else if (v != t)
{
Low[u] = min(Low[u], Low[v]);
}
}
}
int main()
{
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int N, M, x, y;
vector<int> I;
pair< vector<int>, vector< set<int> > > O;
fin >> N >> M;
I.push_back(N);
I.push_back(M);
while (M--)
{
fin >> x >> y;
I.push_back(x);
I.push_back(y);
}
Biconnectivity mflow(I, O);
fout << O.second.size() << '\n';
for (vector< set<int> >::iterator i = O.second.begin(); i != O.second.end(); ++i)
{
for (set<int>::iterator j = i->begin(); j != i->end(); ++j)
{
fout << *j << ' ';
}
fout << '\n';
}
fin.close();
fout.close();
return 0;
}