Pagini recente » Cod sursa (job #2698339) | Cod sursa (job #1817606)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int N, M, V[100003];
vector < vector < int > > sol;
vector < int > G[100003], lev, minlev;
stack < pair < int, int > > S;
void create (int x, int y)
{
vector < int > aux;
aux.resize(0);
int a, b;
do
{
a = S.top().first;
b = S.top().second;
S.pop();
aux.push_back(b);
}
while (a != x or b != y);
aux.push_back(x);
sol.push_back(aux);
}
void DFS (int node, int l)
{
V[node] = 1;
minlev[node] = lev[node] = l;
for (vector < int > :: iterator it = G[node].begin (), sf = G[node].end(); it != sf; ++ it)
{
if (!V[*it])
{
S.push (make_pair (node, *it));
DFS (*it, 1 + l);
minlev[node] = min(minlev[node], minlev[*it]);
if (minlev[*it] >= lev[node])
create (node, *it);
}
else minlev[node] = min(minlev[node], lev[*it]);
}
}
int main ()
{
fin >> N >> M;
minlev.resize(N);
lev.resize(N);
for (int x, y, i = 1; i <= M; ++ i)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= N; ++ i)
{
if (!V[i])
DFS (i, 0);
}
fout << sol.size() << '\n';
for (int i = 0; i < sol.size(); ++ i)
{
for (int j = 0; j < sol[i].size(); ++ j)
{
fout << sol[i][j] << ' ';
}
fout << '\n';
}
fout.close();
return 0;
}