Pagini recente » Cod sursa (job #2415326) | Cod sursa (job #2874676) | Cod sursa (job #540858) | Cod sursa (job #1930532) | Cod sursa (job #2983269)
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> adj[NMAX];
int disc[NMAX], minn[NMAX];
int timp, cnt_cmp = 0;
bool art[NMAX];
vector <int> conex[NMAX];
stack <int> st;
void adauga(int x, int y, int nr)
{
while (st.top() != y)
{
conex[nr].push_back(st.top());
st.pop();
}
conex[nr].push_back(y);
st.pop();
conex[nr].push_back(x);
}
void dfs(int nod, int last)
{
++timp;
disc[nod] = minn[nod] = timp;
int nr = 0;
st.push(nod);
for (int i = 0; i < adj[nod].size(); ++i)
{
int vecin = adj[nod][i];
if (vecin != last)
{
if (disc[vecin] == 0)
{
dfs(vecin, nod);
++nr;
minn[nod] = min(minn[nod], minn[vecin]);
if (minn[vecin] >= disc[nod])
{
++cnt_cmp;
adauga(nod, vecin, cnt_cmp);
//art[nod] = true;
}
}
else
{
minn[nod] = min(minn[nod], disc[vecin]);
}
}
}
}
int main()
{
int n, m, i, j, a, b;
in >> n >> m;
for (i = 1; i <= m; ++i)
{
in >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (i = 1; i <= n; ++i)
{
if (disc[i] == 0)
{
dfs(i, 0);
}
}
out << cnt_cmp << '\n';
for (i = 1; i <= cnt_cmp; ++i)
{
for (j = 0; j < conex[i].size(); ++j)
out << conex[i][j] << " ";
out << '\n';
}
return 0;
}