Pagini recente » Cod sursa (job #3033107) | Cod sursa (job #1100747) | Cod sursa (job #1530337) | Cod sursa (job #1362754) | Cod sursa (job #2764040)
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
vector<int> a[100001];
void read() {
int i, x, y;
ifstream f("biconex.in");
f >> n >> m;
for (i = 1; i <= m; i++) {
f >> x >> y;
a[x].emplace_back(y);
a[y].emplace_back(x);
}
}
int dfn[100001], low[100001];
stack<pair<int, int>> st;
int art[100001];
vector<int> compbiconex[100001];
int aux[100001];
int nrbiconex, lung;
void count(int px, int x) {
int cpx, cx;
lung = 0;
do {
cpx = st.top().first, cx = st.top().second;
st.pop();
aux[++lung] = cpx, aux[++lung] = cx;
} while(px != cpx || cx != x);
sort(aux + 1, aux + lung + 1);
nrbiconex++;
compbiconex[nrbiconex].emplace_back(aux[1]);
for (int i = 2; i <= lung; i++)
if (aux[i] != aux[i - 1])
compbiconex[nrbiconex].emplace_back(aux[i]);
}
void dfs(int x, int px, int nr) {
int i;
dfn[x] = low[x] = nr;
for (i = 0; i < a[x].size(); i++) {
if (px == a[x][i])
continue;
if (dfn[a[x][i]] == 0) {
st.push({x, a[x][i]});
dfs(a[x][i], x, nr + 1);
low[x] = min(low[x], low[a[x][i]]);
if (low[a[x][i]] >= dfn[x]) {
art[x] = 1;
count(x, a[x][i]);
}
}
else low[x] = min(low[x], dfn[a[x][i]]);
}
}
void output() {
int i, j;
ofstream g("biconex.out");
g << nrbiconex << '\n';
for (i = 1; i <= nrbiconex; i++, g << '\n') {
sort(compbiconex[i].begin(), compbiconex[i].end());
for (j = 0; j < compbiconex[i].size(); j++)
g << compbiconex[i][j] << ' ';
}
g.close();
}
int main() {
read();
dfs(1, 0, 1);
output();
return 0;
}