Pagini recente » Cod sursa (job #1794669) | Cod sursa (job #813036) | Cod sursa (job #1495768) | Cod sursa (job #1025163) | Cod sursa (job #988146)
Cod sursa(job #988146)
#include <fstream>
#include <vector>
#define inf 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout ("biconex.out");
vector <int> G[inf],CB[inf];
int stack[inf],lvl[inf];
int n,nrb,a,b,m,t;
bool vis[inf];
int dfs (int x)
{
vis[x]=1;
stack[++t] = x;
int lowlink=inf,child_lowlink;
lvl[x]=t;
for (vector <int>::iterator it=G[x].begin();it!=G[x].end(); ++it)
{
if (!vis[*it])
{
child_lowlink=inf;
child_lowlink = min (child_lowlink,dfs(*it));
if (child_lowlink >= lvl[x])
{
++nrb;
for (; stack[t]!=*it; --t)
{
CB[nrb].push_back (stack[t]);
}
CB[nrb].push_back(stack[t]);
--t;
CB[nrb].push_back(x);
}
lowlink = min (lowlink,child_lowlink);
}
else
{
lowlink = min (lowlink,lvl[*it]);
}
}
return lowlink;
}
int main()
{
fin>>n>>m;
for (int i=1; i<=m; ++i)
{
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
// for (int i=1; i<=n; ++i) lvl[i]=inf;
dfs (1);
fout<<nrb<<"\n";
for (int i=1; i<=nrb; ++i)
{
for (vector<int>::iterator it= CB[i].begin(); it!=CB[i].end(); ++it)
{
fout<<*it<<" ";
}
fout<<"\n";
}
}