Pagini recente » Cod sursa (job #1242135) | Cod sursa (job #2892839) | Cod sursa (job #1534281) | Cod sursa (job #678335) | Cod sursa (job #1168763)
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int **niv, k;
vector <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_back(comp.top().second);
if(comp.top().first==x)
break;
comp.pop();
}
com[k].push_back(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 = new int* [2];
niv[0]=new int [n];
niv[1]=new int [n];
com = new vector<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++)
{
sort(com[i].begin(), com[i].end());
for(int j=0; j<com[i].size(); j++)
o<<com[i][j]+1<<" ";
o<<"\n";
}
return 0;
}