Pagini recente » Cod sursa (job #2179151) | Cod sursa (job #2557161) | Cod sursa (job #2383651) | Cod sursa (job #3237898) | Cod sursa (job #2857080)
#include <vector>
#include <fstream>
#include <bitset>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector < vector <int> > g;
vector <int> dist, low;
vector < vector <int> > cmp;
bitset <100005> viz;
stack <int> s;
int n, m, nrc;
void citire()
{
fin>>n>>m;
g = vector < vector <int> > (n+2);
dist = vector <int> (n+2);
low = vector <int> (n+2);
int x, y;
for (int i=1; i<=m; ++i)
{
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
}
void dfs(int x, int f, int r)
{
viz[x]=1;
dist[x]=low[x]=dist[f]+1;
s.push(x);
int kids=0;
for (auto y:g[x])
{
if (y==f) continue;
if (viz[y])
{
low[x]=min(low[x], dist[y]);
continue;
}
kids++;
dfs(y, x, r);
low[x]=min(low[x], low[y]);
if (dist[x]<=low[y])
{
nrc++;
cmp.push_back( vector <int> (0));
int z;
do
{
z=s.top(); s.pop();
cmp[nrc-1].push_back(z);
} while (z!=y);
cmp[nrc-1].push_back(x);
}
}
}
void solve()
{
for (int i=1; i<=n; ++i)
if (!viz[i]) dfs(i, 0, i);
fout<<nrc<<'\n';
for (int i=0; i<nrc; ++i)
{
for(auto x:cmp[i]) fout<<x<<' ';
fout<<'\n';
}
}
int main()
{
citire();
solve();
return 0;
}