Pagini recente » Cod sursa (job #1283728) | Cod sursa (job #1037200) | Cod sursa (job #1783360) | Cod sursa (job #1430648) | Cod sursa (job #2097709)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconexe.in");
ofstream fout("biconexe.out");
vector<int> a[100001];
int noduri[100001];
int n, m, x, y;
vector<int> cmp[100001];
stack<pair<int, int> > st;
int cmp_len = 0;
template <class T>
void init_array(T a[], int n, T val)
{
for (int i = 0; i < n; i++)
a[i] = val;
}
int bfs(int parrent, int nod, int len)
{
int mn = 0;
noduri[0] = 0x7fffffff;
noduri[nod] = len;
for (unsigned int i = 0; i < a[nod].size(); i++)
{
int fiu = a[nod][i];
if (noduri[fiu] == -1)
{
st.push(make_pair(nod, fiu));
int mini = bfs(nod, fiu, len + 1);
if (noduri[mini] < noduri[mn])
mn = mini;
if (noduri[mini] > len || (noduri[mini] == len && nod != parrent))
{
while (st.top().first != nod || st.top().second != fiu)
{
cmp[cmp_len].push_back(st.top().second);
st.pop();
}
cmp[cmp_len].push_back(st.top().second);
cmp[cmp_len++].push_back(st.top().first);
st.pop();
}
}
else if (noduri[fiu] < noduri[mn] && fiu != parrent)
mn = fiu;
}
return mn;
}
int main()
{
fin >> n >> m;
for (int i = 0; i < m; i++)
{
fin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
init_array(noduri, n + 1, -1);
bfs(1, 1, 0);
if (st.size())
{
while (st.size() > 1)
{
cmp[cmp_len].push_back(st.top().second);
st.pop();
}
cmp[cmp_len].push_back(st.top().second);
cmp[cmp_len++].push_back(st.top().first);
}
fout << cmp_len << '\n';
for (int i = 0; i < cmp_len; i++)
{
for (unsigned int j = 0; j < cmp[i].size(); j++)
fout << cmp[i][j] << ' ';
fout << '\n';
}
return 0;
}