Pagini recente » Cod sursa (job #2542948) | Cod sursa (job #2787871) | Cod sursa (job #2562778) | Cod sursa (job #771816) | Cod sursa (job #2882875)
#include <bits/stdc++.h>
using namespace std;
int n,m,mn[100005],niv[100005],nr;
vector<int>vecini[100005];
stack< pair<int,int> > muchii;
vector<int>ans[100005];
void componenta(int a,int b)
{
vector<int>elem;
while(!muchii.empty())
{
int x=muchii.top().first;
int y=muchii.top().second;
muchii.pop();
elem.push_back(x);
elem.push_back(y);
if(x==a&&y==b) break;
}
sort(elem.begin(),elem.end());
nr++;
ans[nr].push_back(elem[0]);
for(int i=1; i<elem.size(); i++)
if(elem[i]!=elem[i-1]) ans[nr].push_back(elem[i]);
}
void dfs(int nod,int tata)
{
niv[nod]=niv[tata]+1;
mn[nod]=niv[nod];
for(int i=0; i<vecini[nod].size(); i++)
{
int x=vecini[nod][i];
if(x==tata) continue;
if(niv[x]==0)
{
muchii.push({nod,x});
dfs(x,nod);
mn[nod]=min(mn[nod],mn[x]);
if(mn[x]>=niv[nod]) componenta(nod,x);
}
else
{
mn[nod]=min(mn[nod],niv[x]);
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
f>>x>>y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
dfs(1,0);
g<<nr<<'\n';
for(int i=1; i<=nr; i++)
{
for(int j=0; j<ans[i].size(); j++)
g<<ans[i][j]<<' ';
g<<'\n';
}
f.close();
g.close();
return 0;
}