Pagini recente » Cod sursa (job #130044) | Cod sursa (job #2047185) | Cod sursa (job #2583440) | Cod sursa (job #1046706) | Cod sursa (job #2097707)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("componentebiconexe.in");
ofstream fout("componentebiconexe.out");
vector<int> a[100001];
int noduri[100001], len_s;
int n, m, x, y;
//bool art[100001];
vector<int> cmp[100001];
//vector<pair<int, int> > muchii;
stack<pair<int, int> > st;
int cmp_len = 0, muchii_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))
{
/*if (noduri[mini] > len)
{
muchii.push_back(make_pair(nod, fiu));
}
art[nod] = 1;*/
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;
}
//if (a[nod].size() < 2 && parrent == nod) art[nod] = false;
return mn;
}
int main()
{
int p = 1;
//fin >> p >> n >> m;
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);
}
if (p == 1)
{
fout << cmp_len << '\n';
for (int i = 0; i < cmp_len; i++)
{
//fout << cmp[i].size() << ' ';
for (unsigned int j = 0; j < cmp[i].size(); j++)
fout << cmp[i][j] << ' ';
fout << '\n';
}
}
/*else if (p == 2)
{
int cnt = 0;
for (int i = 1; i <= n; i++)
if (art[i]) cnt++;
fout << cnt << '\n';
for (int i = 1; i <= n; i++)
if (art[i]) fout << i << ' ';
}
else if (p == 3)
{
fout << muchii.size() << '\n';
for (int i = 0; i < muchii.size(); i++)
fout << muchii[i].first << ' ' << muchii[i].second << '\n';
}*/
return 0;
}