Pagini recente » Cod sursa (job #486276) | Cod sursa (job #564111) | Cod sursa (job #641054) | Cod sursa (job #2604156) | Cod sursa (job #1393343)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define NMAX 100007
vector < int > G[NMAX];
vector < vector < int > > tow;
vector < vector < int > > :: iterator it;
vector < int > sol;
stack < pair < int , int > > st;
int low[NMAX] , d[NMAX];
// d[node] = adancimea nodului
// low[node] = nivelul minim cu maxim o latura de intoarcere din subarborele lui
int N,M,i,j,x,y;
void df(int node,int father)
{
vector < int > :: iterator it;
d[node] = low[node] = d[father] + 1;
for (it=G[node].begin();it!=G[node].end();++it)
{
int c = *it;
if (c != father && d[c]<d[node])
st.push(make_pair(node,c));
if (d[c] == -1) // nu a fost vizitat
{
df(c,node);
low[node] = min(low[node] , low[c]);
if (d[node] <= low[c])
{
if (st.top() == make_pair(node , c))
sol.push_back(c);
sol.push_back(st.top().first);
while (st.top() != make_pair(node,c))
{
st.pop();
sol.push_back(st.top().first);
}
st.pop();
sort(sol.begin(),sol.end());
sol.resize(distance(sol.begin(),unique(sol.begin(),sol.end())));
tow.push_back(sol);
sol.clear();
}
}
else if (c != father)
low[node] = min (low[node] , d[c]);
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>N>>M;
for (i=1;i<=M;++i)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for (i=1;i<=N;++i)
d[i] = -1;
df(1,0);
g<<tow.size()<<'\n';
for (it=tow.begin();it!=tow.end();++it)
{
sol = *it;
for (j=0;j<sol.size();++j)
g<<sol[j]<<" ";
g<<'\n';
}
return 0;
}