Pagini recente » Cod sursa (job #1544589) | Cod sursa (job #2456814) | Cod sursa (job #574678) | Cod sursa (job #2330596) | Cod sursa (job #1952795)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n, m, x, y, nrc, low[100001], niv[100001];
bool viz[100001];
vector<int> v[100001], comp[100001];
stack<int>st;
void dfs (int nod) {
vector<int>::iterator i;
viz[nod] = 1; low[nod] = niv[nod];
st.push(nod);
for (i = v[nod].begin(); i != v[nod].end(); i++)
if (viz[*i])
low[nod] = min(low[nod], niv[*i]);
else {
niv[*i] = niv[nod]+1;
dfs(*i);
low[nod] = min(low[nod], low[*i]);
if (low[*i] >= niv[nod]) {
nrc++;
while (st.top() != (*i))
comp[nrc].push_back(st.top()), st.pop();
comp[nrc].push_back(st.top()), st.pop();
comp[nrc].push_back(nod);
}
}
}
int main () {
ifstream fi("biconex.in");
ofstream fo("biconex.out");
fi >> n >> m;
for (int i = 1; i <= m; i++)
fi >> x >> y, v[x].push_back(y), v[y].push_back(x);
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
fo << nrc << '\n';
for (int i = 1; i <= nrc; i++) {
vector<int>::iterator j;
for (j = comp[i].begin(); j != comp[i].end(); j++)
fo << (*j) << ' ';
fo << '\n';
}
return 0;
}