Pagini recente » Cod sursa (job #623285) | Cod sursa (job #313674) | Cod sursa (job #364763) | Cod sursa (job #413010) | Cod sursa (job #3215595)
// #include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define pb push_back
// #define fin cin
// #define fout cout
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 1e5;
vector<int> edge[nmax + 1];
vector<vector<int>> bic;
vector<bool> viz(nmax + 1);
vector<int> lvl(nmax + 1);
stack<pair<int, int>> stk;
int n, m, x, y;
void read() {
fin >> n >> m;
for(int i = 1; i <= m; i++) {
fin >> x >> y;
edge[x].pb(y);
edge[y].pb(x);
}
}
void insert_(int node) {
bic.pb(vector<int>());
int padre = stk.top().second;
while(!stk.empty() && padre != node) {
bic.back().pb(stk.top().second);
padre = stk.top().first;
stk.pop();
}
bic.back().pb(node);
}
int dfs(int node) {
viz[node] = 1;
int highest = lvl[node] - 1;
for(auto fiul : edge[node]) {
if(viz[fiul])
highest = min(highest, lvl[fiul]);
else {
lvl[fiul] = lvl[node] + 1;
stk.push({node, fiul});
int fiulrez = dfs(fiul);
if(fiulrez == lvl[node]) {
insert_(node);
} else
highest = min(highest, fiulrez);
}
}
return highest;
}
int main() {
read();
dfs(1);
fout << bic.size() << "\n";
for(int i = 0; i < bic.size(); i++) {
for(auto val : bic[i])
fout << val << " ";
fout << "\n";
}
return 0;
}