Pagini recente » Cod sursa (job #1406942) | Cod sursa (job #1862605) | Cod sursa (job #2171474) | Cod sursa (job #354730) | Cod sursa (job #1864315)
#include <iostream>
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#include <algorithm>
#define dim 100005
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
stack < pair < int,int > > st;
bitset < dim > viz;
vector < vector < int > > lista;
vector < int > gr[dim];
int low[dim],niv[dim],k,n,m,i,x,y;
inline void adaugaComponenta(int x,int y)
{
k++;
vector < int > new_vec;
int xx = 0 ,yy = 0;
while(x != xx || y != yy) // ajung la muchia critica
{
xx = st.top().first;
yy = st.top().second;
new_vec.push_back(xx);
new_vec.push_back(yy);
st.pop();
}
sort(new_vec.begin(),new_vec.end());
lista.push_back(new_vec);
}
inline void dfs(int nod,int nivel)
{
int val = 0;
if(not st.empty())
val = st.top().second;
low[nod] = nivel;
viz [nod] = true;
int l = gr[nod].size();
for(int i = 0; i < l; i++)
if(not viz[gr[nod][i]])
{
int new_nod = gr[nod][i];
st.push( {new_nod , nod});
dfs(new_nod,nivel + 1);
low[nod] = min(low[nod],low[ new_nod ]);
if(low[new_nod] >= nivel)
adaugaComponenta(new_nod,nod);
}
else if(gr[nod][i] != val) low[nod] = min(low[gr[nod][i]],low[nod]);
}
int main()
{
ios::sync_with_stdio(false);
f >> n >> m;
for(i = 1; i <= m; i++)
{
f >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
dfs(1,1);
g << k << '\n';
vector < int > :: iterator it;
for(i = 0; i < k; i++)
{
for(it = lista[i].begin(); it != lista[i].end(); it++)
if(*it != *(it + 1))
g << *it << " ";
g << '\n';
}
return 0;
}