Pagini recente » Cod sursa (job #1794513) | Cod sursa (job #1796188) | Cod sursa (job #1314977) | Cod sursa (job #1717832) | Cod sursa (job #791092)
Cod sursa(job #791092)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
#define MAX 131072
using namespace std;
vector<int> v[MAX], lvl, highest;
vector< vector < int > > sol;
stack< pair < int , int > > stk;
int n, m, a, b, ap[MAX];
void addSolution(int x, int y)
{
vector<int> s; int X, Y;
do
{
X = stk.top().first; Y = stk.top().second;
s.push_back(X); s.push_back(Y);
stk.pop();
} while(X != x || Y != y);
sol.push_back(s);
}
void df(int nod, int dad, int level)
{
lvl[nod] = highest[nod] = level;
for(int i = 0; i < v[nod].size(); i++)
{
if(v[nod][i] == dad) continue;
if(lvl[v[nod][i]] == -1)
{
stk.push(make_pair(nod, v[nod][i]));
df(v[nod][i], nod, level + 1);
highest[nod] = min(highest[nod], highest[v[nod][i]]);
if(lvl[nod] <= highest[v[nod][i]])
addSolution(nod, v[nod][i]);
}
else
highest[nod] = min(highest[nod], lvl[v[nod][i]]);
}
}
int main()
{
ifstream in("biconex.in");
in>>n>>m;
lvl.assign(n + 1, -1);
highest.assign(n + 1, -1);
for(int i = 1; i <= m; i++)
{
in>>a>>b;
v[a].push_back(b); v[b].push_back(a);
}
in.close();
df(1, 0, 0);
ofstream out("biconex.out");
out<<sol.size()<<"\n";
for(int i = 0; i < sol.size(); i++)
{
sort(sol[i].begin(), sol[i].end());
sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
for(int j = 0; j < sol[i].size(); j++)
out<<sol[i][j]<<" ";
out<<"\n";
}
out.close();
return 0;
}