Pagini recente » Cod sursa (job #1116836) | Cod sursa (job #1631459) | Cod sursa (job #423216) | Cod sursa (job #780961) | Cod sursa (job #1168760)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int **niv, k;
vector <int> com[1000001];
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];
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].back()+1<<" ";
com[i].pop_back();
}
o<<"\n";
}
return 0;
}