Pagini recente » Cod sursa (job #2222476) | Cod sursa (job #2006914) | Cod sursa (job #1514093) | Cod sursa (job #2974967) | Cod sursa (job #3222166)
using namespace std;
#include<iostream>
#include <fstream>
#include<vector>
#include<stack>
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, x, y;
vector<int> G[100005];
int d[100005]; ///numarul de ordine al nodului
int low[100005]; ///primul varf ce poate fi atins pe un lant alternativ
int tata[100005]; ///tatal nodului
bool viz[100005];
int timp;
stack<pair<int,int>> st;
vector<int> c;
vector< vector<int> > comp;
void read() {
fin >> n >> m;
for (int i = 1; i<=m; i++) {
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs_l(int nod) {
low[nod] = d[nod] = ++timp; ///initializez low cu timpul de ajungere in nod
for (auto k: G[nod]) {
if (d[k] == 0) { ///nu am vizitat k
tata[k] = nod;
dfs_l(k);
low[nod] = min(low[nod], low[k]); ///compar cu nodul la care poate ajunge k
} else if (k != tata[nod]) {
low[nod] = min(low[nod], d[k]); ///am mai vizitat nodul, am ajuns la el pe un lant alternativ
}
}
}
void creare_componenta(int a, int b) {
c.clear();
int nod = st.top().first, fiu = st.top().second;
while (nod != a || fiu != b) {
c.push_back(fiu);
st.pop();
nod = st.top().first, fiu = st.top().second;
}
st.pop();
c.push_back(fiu);
c.push_back(nod);
comp.push_back(c);
}
void dfs(int nod) {
viz[nod] = 1;
for (auto k: G[nod]) {
if (!viz[k]) {
st.push({nod, k}); ///adaug muchie
dfs(k);
if (low[k] >= d[nod]) { ///nod este punct de articulatie, nu pot ajunge din k la noduri mai sus ca el
creare_componenta(nod, k);
}
}
}
}
void solve() {
for (int i = 1; i<=n; i++) {
if (d[i] == 0) {
dfs_l(i);
}
}
for (int i = 1; i<=n; i++) {
if (!viz[i]) {
dfs(i);
}
}
}
void print() {
fout << comp.size() << "\n";
for (auto x: comp) {
for (auto y: x) {
fout << y << " ";
}
fout << "\n";
}
}
int main() {
read();
solve();
print();
return 0;
}