Pagini recente » Rating infoarena | Cod sursa (job #2219660) | Cod sursa (job #2323146) | Cod sursa (job #3294794) | Cod sursa (job #3293535)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
using oset=tree<int,null_type,std::less<int>,rb_tree_tag,tree_order_statistics_node_update>;
#define all(x) x.begin(),x.end()
using i64 =long long;
const int N_MAX=1e5;
const int inf=1e9;
int n,m;
int tin[N_MAX],low[N_MAX];
std::vector<int>adj[N_MAX];
std::stack<std::pair<int,int>>sk;
std::vector<std::vector<int>>comps;
void pop_till(int x,int y)
{
std::vector<int>aux;
while(sk.top().first!=x || sk.top().second!=y)
{
aux.push_back(sk.top().first);
aux.push_back(sk.top().second);
sk.pop();
}
aux.push_back(x);
aux.push_back(y);
sk.pop();
std::sort(all(aux));
aux.erase(std::unique(all(aux)),aux.end());
comps.push_back(aux);
}
void dfs(int nod,int tt)
{
static int time=0;
tin[nod]=low[nod]=++time;
for(auto &c:adj[nod])
{
if(c==tt)
{
continue;
}
if(low[c]==0)
{
sk.push({nod,c});
dfs(c,nod);
low[nod]=std::min(low[nod] , low[c]);
if(low[c]>=tin[nod])
{
pop_till(nod,c);
}
}
else
{
low[nod]=std::min(low[nod] , tin[c]);
}
}
}
[[gnu::optimize("O3")]]signed main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y;
std::cin>>x>>y;
x--;
y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(0,0);
std::cout<<comps.size()<<'\n';
for(auto &v:comps)
{
for(auto &c:v)
{
std::cout<<c+1<<' ';
}
std::cout<<'\n';
}
return 0;
}