Pagini recente » Cod sursa (job #1742808) | Cod sursa (job #493526) | Cod sursa (job #2141150) | Cod sursa (job #890778) | Cod sursa (job #2555593)
#include <bits/stdc++.h>
using namespace std;
ifstream inf("biconex.in");
ofstream outf("biconex.out");
int n, m, cbx;
vector<int> v[100010], dfn, low;
vector<int> acb[100010];
stack<pair<int,int>> s;
void dfs(int ,int ,int );
int main()
{
inf>>n>>m;
for(int i=1; i<=m; i++)
{
int x, y;
inf>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfn.resize(n+1);
dfn.assign(n+1, -1);
low.resize(n+1);
dfs(1, 0, 0);
outf<<cbx<<'\n';
for(int i=1; i<=cbx; i++)
{
sort(begin(acb[i]), end(acb[i]));
acb[i].erase(unique(acb[i].begin(), acb[i].end()), acb[i].end());
for(auto it:acb[i])
outf<<it<<' ';
outf<<'\n';
}
return 0;
}
void dfs(int n, int fn, int nr)
{
dfn[n]=low[n]=nr;
for(auto it:v[n])
{
if(it==fn)
continue;
if(dfn[it]==-1)
{
s.push({n,it});
dfs(it, n, nr+1);
low[n]=min(low[n], low[it]);
if(low[it]>=dfn[n])
{
cbx++;
int tx, ty;
do
{
tx=s.top().first;
ty=s.top().second;
s.pop();
acb[cbx].push_back(tx);
acb[cbx].push_back(ty);
}while(tx!=n||ty!=it);
}
}
else
low[n]=min(low[n], dfn[it]);
}
}