Pagini recente » Clasament dupa rating | Cod sursa (job #1103706) | Cod sursa (job #608746) | Cod sursa (job #941440) | Cod sursa (job #3211700)
#include <bits/stdc++.h>
#define pb push_back
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<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>());
while(!stk.empty() && stk.top() != node) {
bic.back().pb(stk.top());
stk.pop();
}
bic.back().pb(node);
reverse(bic.back().begin(), bic.back().end());
}
int dfs(int node) {
viz[node] = 1;
stk.push(node);
int highest = lvl[node] - 1;
for(auto fiul : edge[node]) {
if(viz[fiul])
highest = min(highest, lvl[fiul]);
else {
lvl[fiul] = lvl[node] + 1;
int fiulrez = dfs(fiul);
if(fiulrez >= lvl[node])
insert_(node);
else
highest = min(highest, fiulrez);
}
}
return highest;
}
int main() {
read();
edge[0].pb(1);
lvl[0] = 0;
dfs(0);
bic.pop_back();
fout << bic.size() << "\n";
for(int i = 0; i < bic.size(); i++) {
for(auto val : bic[i])
fout << val << " ";
fout << "\n";
}
return 0;
}