Pagini recente » Cod sursa (job #303812) | Cod sursa (job #2903193) | Cod sursa (job #460694) | Cod sursa (job #621105) | Cod sursa (job #2199296)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int kMax = 100001;
int n, m, d[kMax], low[kMax], nrb = 0, times = 0;
vector<int> v[kMax], G[kMax];
stack< pair<int, int> >stk;
pair<int, int> pa;
void DFSs(int k, int ×) {
d[k] = ++times;
low[k] = d[k];
for (int i = 0; i < G[k].size(); i++) {
if (d[G[k][i]] == 0) {
stk.push(make_pair(k, G[k][i]));
DFSs(G[k][i], times);
low[k] = min(low[k], low[G[k][i]]);
if (low[G[k][i]] >= d[k]) {
nrb++;
pa = stk.top();
while (pa.first != k) {
v[nrb].push_back(pa.second);
stk.pop();
pa = stk.top();
}
stk.pop();
v[nrb].push_back(pa.first);
v[nrb].push_back(pa.second);
sort(v[nrb].begin(), v[nrb].end());
}
}
else {
low[k] = min(low[k], d[G[k][i]]);
}
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for (int i = 1; i <= n; i++)
if (d[i] == 0)
DFSs(i, times);
fout << nrb << '\n';
for (int i = 1; i <= nrb; i++){
for (int j = 0; j < v[i].size(); j++)
fout << v[i][j] << " ";
fout << '\n';
}
fin.close();
fout.close();
return 0;
}