Pagini recente » Cod sursa (job #803436) | Cod sursa (job #1556660) | Cod sursa (job #2443891) | Cod sursa (job #688005) | Cod sursa (job #2899896)
/// always:
#include <cstdio>
#include <string>
/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
bool home = 1;
using namespace std;
typedef long double ld;
const string TASKNAME="biconex";
const int N=(int)1e5+7;
int n;
int m;
vector<int> g[N];
int dep[N];
int mindep[N];
vector<int> verts;
vector<vector<int>> sol;
void dfs(int a) {
verts.push_back(a);
mindep[a]=dep[a];
for (auto &b:g[a]) {
if (dep[b]==-1) {
dep[b]=1+dep[a];
int pos_start=(int)verts.size();
dfs(b);
mindep[a]=min(mindep[a],mindep[b]);
if (mindep[b]>dep[a]) {
vector<int> cur;
while ((int)verts.size()>pos_start){
cur.push_back(verts.back());
verts.pop_back();
}
sol.push_back({a, b});
if ((int)cur.size()>1) sol.push_back(cur);
}
continue;
}
if (dep[b]<dep[a]-1) {
mindep[a]=min(mindep[a],dep[b]);
}
}
}
signed main() {
#ifdef INFOARENA
home = 0;
#endif
if(!home) {
freopen((TASKNAME + ".in").c_str(), "r", stdin);
freopen((TASKNAME + ".out").c_str(), "w", stdout);
}else{
freopen ("I_am_iron_man", "r", stdin);
}
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
}
for (int i=1;i<=n;i++) dep[i]=-1;
dep[1]=0;
dfs(1);
if ((int)verts.size()>1) sol.push_back(verts);
cout<<(int)sol.size()<<"\n";
for (auto &v:sol) {
sort(v.begin(),v.end());
for (auto &x:v){
cout<<x<<" ";
}
cout<<"\n";
}
}