Pagini recente » Cod sursa (job #901994) | Cod sursa (job #2885567) | Cod sursa (job #2446047) | Cod sursa (job #1542623) | Cod sursa (job #2408107)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int maxn = 2e5+2;
int n, m, level[maxn], low[maxn], st;
pair<int, int>stk[maxn*2];
vector<int>G[maxn];
vector<vector<int> >R;
void sterge(int nod1, int nod2)
{
vector<int>comp;int x, y;
do
{
x=stk[st].first;
y=stk[st].second;
st--;
comp.push_back(x);
comp.push_back(y);
}while(x!=nod1 || y!=nod2);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(),comp.end()), comp.end());
R.push_back(comp);
}
void dfs(int nod, int tata, int nivel)
{
level[nod]=low[nod]=nivel;
for(auto it:G[nod])
{
if(it!=tata)
{
if(level[it]==0)
{
++st;
stk[st].first=nod;
stk[st].second=it;
dfs(it, nod, nivel+1);
low[nod]=min(low[nod], low[it]);
if(low[it]>=level[nod])
{
sterge(nod, it);
}
}
else
{
low[nod]=min(low[nod], level[it]);
}
}
}
}
int main()
{
int x, y;
fin>>n>>m;
for(int i=1; i<=m; i++)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0, 1);
fout<<R.size()<<'\n';
for(int i=0; i<R.size(); i++)
{
for(auto it:R[i])
{
fout<<it<<' ';
}
fout<<'\n';
}
return 0;
}