Pagini recente » Cod sursa (job #2892953) | Cod sursa (job #502037) | Cod sursa (job #182598) | Cod sursa (job #41056) | Cod sursa (job #3225545)
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define vpi vector<pii>
#define vvpi vector<vpi>
#define ll long long
#define double long double
#define eb emplace_back
#define lo(x) (2 * (x) - 1)
#define up(x) (2 * (x))
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
const string TASK("biconex");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout
const int N = 1e5 + 9, Inf = 0x3f3f3f3f;
int n, m;
vvi G(N);
int low[N], lvl[N], idx, comp[N], t[N];
stack<pii> stk;
//bool mat[N][N], viz[N];
vvi cbc;
vi c;
void extract_cbc(int x, int y)
{
c.clear();
int a, b;
do
{
a = stk.top().ff, b = stk.top().ss;
stk.pop();
// comp[a] = comp[b] = cbc.size() + 1;
c.pb(a), c.pb(b);
}while(a != x && b != y);
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
cbc.pb(c);
}
void Dfs(int x, int p)
{
low[x] = lvl[x] = ++idx;
for(auto y : G[x])
{
if(y == p)continue;
if(!lvl[y])
{
stk.push({x, y});
Dfs(y, x);
low[x] = min(low[x], low[y]);
if(lvl[x] <= low[y])
extract_cbc(x, y);
}
else low[x] = min(low[x], lvl[y]);
}
}
//vpi ans;
//void Dfs_T(int x = 1, int p = -1)
//{
// viz[x] = true;
//
// if(!t[comp[x]])
// {
// t[comp[x]] = p;
//
// int rep = (x == 1) ? (n + 1) : p;
// for(auto i : cbc[comp[x] - 1])
// if(i != rep)
// ans.pb({i, rep});
// }
//
// for(auto y : G[x])
// if(!viz[y])
// Dfs_T(y, x);
//}
//
//void RESET()
//{
// idx = 0;
// cbc.clear();
// ans.clear();
// FOR(i, 1, n)
// {
// viz[i] = t[i] = low[i] = lvl[i] = comp[i] = 0;
// G[i].clear();
// FOR(j, 1, n)mat[i][j] = 0;
// }
//}
void solve()
{
cin >> n >> m;
int x, y;
FOR(i, 1, m)
{
cin >> x >> y;
G[x].pb(y);
G[y].pb(x);
}
Dfs(1, 0);
cout << cbc.size() << '\n';
for(auto i : cbc)
{
for(auto j : i)cout << j << ' ';
cout << '\n';
}
}
signed main()
{
// cin >> p;
int t = 1;
// cin >> t;
// cout << fixed << setprecision(12);
while(t --)
solve();
return 0;
}