Pagini recente » Cod sursa (job #549980) | Cod sursa (job #1211566) | Cod sursa (job #1055528) | Cod sursa (job #3189314) | Cod sursa (job #2698945)
#define NMAX 100005
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
int lvl[NMAX];
int low[NMAX];
vector<int> G[NMAX];
stack<pair<int, int> > S;
vector<vector<int> > comp;
void get_comp(pair<int, int> edge)
{
vector<int> temp_comp;
while (true)
{
pair <int, int> tp = S.top();
S.pop();
temp_comp.push_back(tp.first);
temp_comp.push_back(tp.second);
if (tp == edge)
break;
}
sort(temp_comp.begin(), temp_comp.end());
temp_comp.erase(unique(temp_comp.begin(), temp_comp.end()), temp_comp.end());
comp.push_back(temp_comp);
temp_comp.clear();
}
void DFS(int node = 1, int parent = 0)
{
low[node] = lvl[node] = lvl[parent] + 1;
for (auto v:G[node])
{
if (v == parent)
continue;
if (!lvl[v])
{
S.push({node, v});
DFS(v, node);
low[node] = min(low[node], low[v]);
if (low[v] >= lvl[node])
get_comp({node, v});
}
else
low[node] = min(low[node], lvl[v]);
}
}
void read()
{
int x, y;
f>>n>>m;
for(int i = 1; i <= m; ++i)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
int main()
{
read();
DFS();
// for(int i = 1; i <= n; ++i)
// g<<low[i]<<" ";
// g<<'\n';
g<<comp.size()<<'\n';
for (auto& c:comp)
{
for (auto v:c)
g<<v<<' ';
g<<'\n';
}
return 0;
}