Pagini recente » Cod sursa (job #498299) | Cod sursa (job #2970313) | Cod sursa (job #2383207) | Cod sursa (job #884901) | Cod sursa (job #2442961)
#include <fstream>
#include <iostream>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <queue>
using namespace std;
ifstream fin ("dmax.in");
ofstream fout ("dmax.out");
vector <int> a[100005];
vector <vector <int> > e;
unordered_set <int> cutVertex;
queue <int> q;
int d[100005], f[100005], disc[100005], low[100005], parent[100005], sz, temp;
pair <int, int> cutEdges[200005];
stack <pair <int, int> > st;
void found(int x, int y)
{
pair <int, int> top;
vector <int> b;
do {
top.first = st.top().first, top.second = st.top().second;
st.pop();
b.push_back(top.first); b.push_back(top.second);
}
while(top.first != x || top.second != y);
e.push_back(b);
}
void dfs(int k)
{
disc[k] = low[k] = ++temp;
for(auto v : a[k]) {
if(!disc[v]) {
st.push(make_pair(k, v));
dfs(v);
low[k] = min(low[k], low[v]);
if(low[v] >= disc[k])
found(k, v);
}
else
low[k] = min(low[k], disc[v]);
}
}
int main()
{
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
dfs(1);
fout << e.size() << "\n";
for(int i = 0; i < e.size(); ++i) {
sort(e[i].begin(), e[i].end());
e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
for(int j = 0; j < e[i].size(); ++j) fout << e[i][j] << " ";
fout << "\n";
}
return 0;
}