Pagini recente » Cod sursa (job #1498352) | Cod sursa (job #1273369) | Cod sursa (job #2343152) | Cod sursa (job #1834135) | Cod sursa (job #2665006)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");
const int MAXN = 100000, MAXM = 200000;
int N, M;
stack <pair <int, int>> st;
int vis[MAXN + 1], low[MAXN + 1];
vector <int> adj[MAXN + 1];
vector <set <int> > C;
void dfs(int curr, int fd, int cnt)
{
low[curr] = cnt;
vis[curr] = cnt;
for (int nbh: adj[curr])
if (nbh != fd)
{
if (vis[nbh] == 0)
{
st.push( make_pair(curr, nbh) );
dfs(nbh, curr, cnt + 1);
low[curr] = min(low[curr], low[nbh]);
if (low[nbh] >= vis[curr])
{
set <int> con;
while (st.top().first != curr || st.top().second != nbh)
{
con.insert(st.top().first);
con.insert(st.top().second);
st.pop();
}
con.insert(curr);
con.insert(nbh);
st.pop();
C.push_back(con);
}
}
else
low[curr] = min(low[curr], vis[nbh]);
}
}
int main()
{
in >> N >> M;
int m1, m2;
for (int i = 0; i < M; ++i)
{
in >> m1 >> m2;
adj[m1].push_back(m2);
adj[m2].push_back(m1);
}
dfs(1, 0, 1);
out << C.size() << "\n";
for (int i = 0; i < C.size(); ++i)
{
for (auto it = C[i].begin(); it != C[i].end(); it++)
out << *it << " ";
out << "\n";
}
}