Pagini recente » Cod sursa (job #1011054) | Cod sursa (job #689) | Cod sursa (job #560385) | Cod sursa (job #210103) | Cod sursa (job #2136903)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 100005
ifstream f("biconex.in");
ofstream g("biconex.out");
struct str
{
int nod1,nod2;
};
vector<int>Q[nmax],componentebiconexe[nmax];
vector<str>stk;
int n,m,low[nmax],lvl[nmax],tata[nmax],ncurent;
void read()
{
f>>n>>m;
for (int i=1; i<=m; ++i)
{
int a,b;
f>>a>>b;
Q[a].push_back(b);
Q[b].push_back(a);
}
}
void afis(int nodd1,int nodd2)
{
while (stk.back().nod1!=nodd1||stk.back().nod2!=nodd2)
{
componentebiconexe[ncurent].push_back(stk.back().nod1);
componentebiconexe[ncurent].push_back(stk.back().nod2);
stk.pop_back();
}
componentebiconexe[ncurent].push_back(stk.back().nod1);
componentebiconexe[ncurent].push_back(stk.back().nod2);
stk.pop_back();
++ncurent;
}
void dfs(int nod)
{
for (auto w:Q[nod])
{
if (tata[nod]==w)
continue;
if (lvl[w]==-1)
{
stk.push_back({nod,w});
low[w]=lvl[w]=lvl[nod]+1;
dfs(w);
low[nod]=min(low[nod],low[w]);
if (low[w]>=lvl[nod])
afis(nod,w);
}
else
low[nod]=min(low[nod],lvl[w]);
}
}
void solve()
{
for (int i=1; i<=n; ++i)
lvl[i]=-1;
tata[1]=-1;
dfs(1);
g<<ncurent<<'\n';
for (int i=0; i<ncurent; ++i)
{
int last=-1;
sort(componentebiconexe[i].begin(),componentebiconexe[i].end());
for (auto w:componentebiconexe[i])
{
if (w==last)
continue;
else
{
g<<w<<' ';
last=w;
}
}
g<<'\n';
}
}
int main()
{
read();
solve();
return 0;
}