Pagini recente » Cod sursa (job #2037921) | Cod sursa (job #1348592) | Cod sursa (job #1797655) | Cod sursa (job #44508) | Cod sursa (job #1862486)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMax = 1e5 + 5;
vector < int > G[NMax];
stack < pair < int, int > > Stack;
vector < vector < int > > Ans;
int level[NMax];
int low[NMax];
inline void AddComponent(const int &a, const int &b) {
vector < int > aux;
int x, y;
do {
x = (Stack.top()).first;
y = (Stack.top()).second;
aux.push_back(x);
aux.push_back(y);
Stack.pop();
} while(x != a || y != b);
Ans.push_back(aux);
}
void DFS(const int &node, const int &lvl) {
level[node] = low[node] = lvl;
for(auto const &i: G[node]) {
if(level[i] == 0) {
Stack.push({node, i});
DFS(i, lvl + 1);
low[node] = min(low[node], low[i]);
if(low[i] >= level[node]) {
AddComponent(node, i);
}
} else {
low[node] = min(low[node], level[i]);
}
}
}
int main() {
ios::sync_with_stdio(false);
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1, 1);
fout << Ans.size() << "\n";
for(auto i: Ans) {
sort(i.begin(), i.end());
i.erase(unique(i.begin(), i.end()), i.end());
for(auto const &j: i) {
fout << j << " ";
}
fout << "\n";
}
return 0;
}