Pagini recente » Cod sursa (job #1224994) | Cod sursa (job #1205753) | Cod sursa (job #2879367) | Cod sursa (job #1557954) | Cod sursa (job #3215610)
#include <bits/stdc++.h>
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].push_back(y);
edge[y].push_back(x);
}
}
void insert_(int node, int cineMA) {
bic.push_back(vector<int>());
int cine = -1;
while(!stk.empty() && cine != cineMA) {
cine = stk.top();
bic.back().push_back(cine);
stk.pop();
}
bic.back().push_back(node);
}
int dfs(int node) {
viz[node] = 1;
int highest = lvl[node] - 1;
stk.push(node);
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, fiul);
} 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;
}