Pagini recente » Cod sursa (job #726368) | Cod sursa (job #2858288) | Cod sursa (job #1514298) | Cod sursa (job #2113945) | Cod sursa (job #3222324)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
using i64=int64_t;
const int inf=1e9;
const int N=1e5;
int low[N],tin[N];
struct Edge
{
int x,y;
};
stack<Edge>sk;
vector<vector<int>>comps;
vector<int>g[N];
int n,m,cnt;
void pop_comp(int x,int y)
{
vector<int>acum;
while(sk.top().x!=x || sk.top().y!=y)
{
acum.pb(sk.top().x);
acum.pb(sk.top().y);
sk.pop();
}
acum.pb(sk.top().x);
acum.pb(sk.top().y);
sk.pop();
comps.pb(acum);
}
int now=1;
void dfs(int nod,int tt)
{
low[nod]=tin[nod]=++now;
for(auto &c:g[nod])
{
if(c==tt)
{
continue;
}
if(!low[c])
{
sk.push({nod,c});
dfs(c,nod);
low[nod]=min(low[nod],low[c]);
if(low[c]>=tin[nod])
{
cnt++;
pop_comp(nod,c);
}
}
else
{
low[nod]=min(low[nod],low[c]);
}
}
}
main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
x--;
y--;
g[x].pb(y);
g[y].pb(x);
}
dfs(0,0);
cout<<comps.size()<<'\n';
assert((int)comps.size()==cnt);
for(auto &v:comps)
{
sort(all(v));
v.erase(unique(all(v)) , v.end());
for(auto &c:v)
{
cout<<c+1<<' ';
}
cout<<'\n';
}
}