Pagini recente » Cod sursa (job #1172878) | Cod sursa (job #1257553) | Cod sursa (job #278660) | Cod sursa (job #99525) | Cod sursa (job #1168754)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int *niv[2], k;
stack <int> *com;
stack <pair<int, int> > comp;
vector <int> *g;
bool *viz;
void dfs (int x, int n)
{
viz[x]=1;
niv[0][x] = n;
niv[1][x] = n;
for(int i = 0; i<g[x].size(); i++)
{
if(!viz[g[x][i]])
{
comp.push(make_pair(x, g[x][i]));
dfs(g[x][i], n+1);
if(niv[0][x] <= niv[1][g[x][i]])
{
for(;;)
{
com[k].push(comp.top().second);
if(comp.top().first==x)
break;
comp.pop();
}
com[k].push(x);
comp.pop();
k++;
}
niv[1][x] = min (niv[1][x], niv[1][g[x][i]]);
}
else
niv[1][x] = min (niv[1][x], niv[0][g[x][i]]);
}
}
int main()
{
int n, m, x, y;
ifstream f("biconex.in");
f>>n>>m;
g = new vector<int> [n];
viz = new bool [n];
niv[0] = new int [n];
niv[1] = new int [n];
com = new stack<int> [n];
for(int i=0; i<m; i++)
{
f>>x>>y;
g[x-1].push_back(y-1);
g[y-1].push_back(x-1);
}
dfs(0, 0);
ofstream o("biconex.out");
o<<k<<"\n";
for(int i=0; i<k; i++)
{
while(!com[i].empty())
{
o<<com[i].top()+1<<" ";
com[i].pop();
}
o<<"\n";
}
return 0;
}