Pagini recente » Cod sursa (job #2796749) | Cod sursa (job #2740656) | Cod sursa (job #346738) | Cod sursa (job #3275564) | Cod sursa (job #2410214)
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
const string file = "biconex";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 100005;
int n, m, dfn[nmax], low[nmax], nrfii, p;
vector<int> v[nmax];
vector< vector<int> > sol;
stack<pi> s;
bool ok[nmax];
void add_sol(int x, int y)
{
sol.push_back(vector<int>());
unordered_set<int> r;
pi now;
do{
now = s.top();
s.pop();
r.insert(now.ff);
r.insert(now.ss);
}while((x != now.ff || y != now.ss) && (x != now.ss || y != now.ff));
for (auto x : r)
sol.back().push_back(x);
}
void dfs(int x)
{
ok[x] = 1;
dfn[x] = ++p;
low[x] = dfn[x];
for (auto y : v[x])
if(!ok[y]){
s.push({x, y});
dfs(y);
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x])
add_sol(x, y);
}else low[x] = min(low[x], dfn[y]);
}
int main()
{
ifstream fin (file+".in");
ofstream fout (file+".out");
fin >> n >> m;
for (int i = 1; i <= m; ++i){
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);
fout << sol.size() << "\n";
for (auto x : sol){
for (auto y : x)
fout << y << " ";
fout << "\n";
}
return 0;
}