Pagini recente » Cod sursa (job #63631) | Cod sursa (job #127582) | Cod sursa (job #664751) | Cod sursa (job #1762721) | Cod sursa (job #1680470)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
#define Nmax 100001
vector< int > G[Nmax];
vector< vector< int > > comp;
//vector< bool > critic(Nmax);
stack< pii > stk;
int low[Nmax], d[Nmax];
int n, time = 0;
void DFS(int, int);
void cache(int, int);
int main()
{
int i, m, a, b;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> n >> m;
for (; m; --m)
{
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for (i = 1; i <= n; ++i)
if (low[i] == 0) DFS(i, 0);
fout << comp.size() << '\n';
for (auto &vec : comp)
{
for (auto &node : vec)
fout << node << ' ';
fout << '\n';
}
return 0;
}
void DFS(int vf, int f)
{
++time;
low[vf] = d[vf] = time;
for (auto &it : G[vf])
{
if (it == f) continue;
if (low[it] == 0)
{
stk.push(make_pair(it, vf));
DFS(it, vf);
if (low[vf] > low[it]) low[vf] = low[it];
if (low[it] >= d[vf]) cache(it, vf);
}
else if (d[it] < low[vf]) low[vf] = d[it];
}
++time;
}
void cache(int vf, int f)
{
int tx, ty;
comp.push_back(vector<int>());
do
{
tx = stk.top().first;
ty = stk.top().second;
comp.back().push_back(tx);
comp.back().push_back(ty);
stk.pop();
} while (ty != f);
sort(comp.back().begin(), comp.back().end());
comp.back().erase(unique(comp.back().begin(), comp.back().end()), comp.back().end());
}