Pagini recente » Cod sursa (job #772134) | Cod sursa (job #1377275) | Cod sursa (job #618969) | Cod sursa (job #2474329) | Cod sursa (job #1884672)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int maxn=100005;
int N,M,nrbicon;
int viz[maxn],low[maxn];
vector <int> G[maxn],bicon[maxn];
stack <int> S;
void dfs(int nod,int prec)
{
int sz=G[nod].size(),i,next;
viz[nod]=viz[prec]+1;
low[nod]=viz[nod];
S.push(nod);
for (i=0;i<sz;i++)
{
next=G[nod][i];
if (viz[next]==0)
{
dfs(next,nod);
low[nod]=min(low[nod],low[next]);
if (viz[nod]<=low[next])
{
while (S.empty()==0 && S.top()!=next)
{
bicon[nrbicon].push_back(S.top());
S.pop();
}
S.pop();
bicon[nrbicon].push_back(next);
bicon[nrbicon].push_back(nod);
nrbicon++;
}
}
else low[nod]=min(low[nod],viz[next]);
}
}
int main()
{
int i,j,x,y;
f>>N>>M;
for (i=1;i<=M;i++)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
g<<nrbicon<<'\n';
for (i=0;i<nrbicon;i++)
{
for (j=0; j<bicon[i].size(); j++)
{
g<<bicon[i][j]<<" ";
}
g<<'\n';
}
}