Pagini recente » Cod sursa (job #322989) | Borderou de evaluare (job #1330295) | Cod sursa (job #70195) | Cod sursa (job #579264) | Cod sursa (job #3193188)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, x, y;
const int NMAX = 100001;
vector<int> a[NMAX];
int dfscnt, dfsnr[NMAX], low[NMAX];
using pii = pair<int, int>;
stack<pii> s;
vector<vector<int>> comp;
void print(int x, int tx) {
vector<int> v;
pii p;
do {
p = s.top();
s.pop();
v.push_back(p.first);
v.push_back(p.second);
} while (p != make_pair(x, tx));
comp.push_back(v);
}
void biconex(int x, int tx) {
dfsnr[x] = ++dfscnt;
low[x] = dfscnt;
for (int p : a[x]) {
if (p == tx) {
continue;
}
if (dfsnr[p] == -1) {
s.push(make_pair(p, x));
biconex(p, x);
low[x] = min(low[x], low[p]);
if (low[p] >= dfsnr[x]) {
print(p, x);
}
} else {
low[x] = min(low[x], dfsnr[p]);
}
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
dfsnr[i] = -1;
low[i] = -1;
}
biconex(1, -1);
fout << comp.size() << "\n";
for (auto& v : comp) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (auto x : v) {
fout << x << " ";
}
fout << "\n";
}
}