Pagini recente » Cod sursa (job #2772795) | Cod sursa (job #2516496) | Cod sursa (job #1162086) | Cod sursa (job #1084762) | Cod sursa (job #2698878)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct Edge{
int a, b;
int ott(int x){
if(x==a)return b;
else if(x==b)return a;
else return 0;
}
};
bool eq(const Edge &lhs, const Edge &rhs){
return lhs.a==rhs.a && lhs.b==rhs.b;
}
const int N = 100041;
const int M = 200041;
int n, m;
vector<int> gra[N];
Edge edg[M];
bool vi[M];
int depth[N];
int lowling[N];
stack<Edge> stak;
set<int> se;
vector<vector<int>> ans;
void dfs(int a){
lowling[a] = depth[a];
for(auto e : gra[a]){
auto &ed = edg[e];
int b = ed.ott(a);
if(!vi[e] && depth[b] == 0){ // Forward edge
stak.push(ed);
vi[e] = true;
depth[b] = depth[a] + 1;
dfs(b);
lowling[a] = min(lowling[a], lowling[b]);
if(lowling[b] >= depth[a]){
while(!stak.empty() && !eq(stak.top(), ed)){
se.insert(stak.top().a);
se.insert(stak.top().b);
stak.pop();
}
se.insert(stak.top().a);
se.insert(stak.top().b);
stak.pop();
ans.push_back({});
auto &v = ans.back();
for(auto a : se){
v.push_back(a);
}
se.clear();
}
}else{ // Backward edge
lowling[a] = min(lowling[a], depth[b]);
}
}
// cout << a << " " << depth[a] << " " << lowling[a] << "\n";
}
int main(){
// ios_base::sync_with_stdio(false);
fin >> n >> m;
for(int i = 1; i <= m; ++i){
int a, b;
fin >> a >> b;
edg[i] = {a,b};
gra[a].push_back(i);
gra[b].push_back(i);
}
depth[1] = 1;
dfs(1);
fout << ans.size() << "\n";
for(auto &v : ans){
for(auto a : v){
fout << a << " ";
}
fout << "\n";;
}
return 0;
}