Pagini recente » Cod sursa (job #1176591) | Cod sursa (job #204096) | Cod sursa (job #301543) | Istoria paginii cn-soft-grigore-moisil/clasament/9-10 | Cod sursa (job #2013549)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int n;
int dfn[100005], low[100005];
vector <int> a[100005];
vector <vector <int> > sol;
stack <pair <int, int> > st;
void afisare(int x, int y)
{
int X, Y;
vector <int> aux;
do
{
X = st.top().first; Y = st.top().second;
st.pop();
aux.push_back(X); aux.push_back(Y);
} while(X != x && Y != y);
sol.push_back(aux);
}
void Biconex(int nc, int pnc, int num)
{
int x;
vector<int>::iterator it;
dfn[nc] = low[nc] = num;
for(it = a[nc].begin(); it != a[nc].end(); ++it)
{
if(*it == pnc) continue;
if(dfn[*it] == -1)
{
st.push(make_pair(nc, *it));
Biconex(*it, nc, num+1);
low[nc] = min(low[nc], low[*it]);
if(low[*it] >= dfn[nc]) afisare(nc, *it);
}
else low[nc] = min(low[nc], dfn[*it]);
}
}
int main()
{
int m;
ifstream fin("biconex.in");
fin >> n >> m;
for(int i = 1, x, y; i <= m; ++i)
{
fin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
fin.close();
for(int i = 1; i <= n; ++i) dfn[i] = -1;
Biconex(1, 0, 0);
ofstream fout("biconex.out");
fout << sol.size() << '\n';
for(int i = 0; i < sol.size(); ++i)
{
sort(sol[i].begin(), sol[i].end());
sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
for(int j = 0; j < sol[i].size(); ++j) fout << sol[i][j] << " ";
fout << '\n';
}
fout.close();
return 0;
}