Pagini recente » Cod sursa (job #2118937) | Cod sursa (job #1669243) | Cod sursa (job #602365) | Cod sursa (job #2245496) | Cod sursa (job #476706)
Cod sursa(job #476706)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
int N, T, M;
vector<int> Dfn, Low;
vector< vector<int> > Deg;
vector< set<int> > Cmp;
stack< pair<int, int> > Stk;
void read()
{
int x, y;
vector<int> Aux;
ifstream fin("biconex.in");
fin >> N >> M;
Deg.assign(N + 1, Aux);
while (M--)
{
fin >> x >> y;
Deg[x].push_back(y);
Deg[y].push_back(x);
}
fin.close();
}
void dfs(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])
{
dfs(v, u);
Low[u] = min(Low[u], Low[v]);
if (Dfn[u] <= Low[v])
{
pair<int, int> p;
Cmp.push_back(set<int>());
do
{
p = Stk.top();
Cmp[Cmp.size() - 1].insert(p.first);
Cmp[Cmp.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]);
}
}
}
void solve()
{
Dfn.assign(N + 1, 0);
Low.assign(N + 1, 0);
Stk.push(pair<int, int>(-1, 1));
dfs(1, -1);
}
void write()
{
ofstream fout("biconex.out");
fout << Cmp.size() << '\n';
for (vector< set<int> >::iterator i = Cmp.begin(); i != Cmp.end(); ++i)
{
for (set<int>::iterator j = i->begin(); j != i->end(); ++j)
{
fout << *j << ' ';
}
fout << '\n';
}
}
int main()
{
read();
solve();
write();
return 0;
}