Pagini recente » Cod sursa (job #1070008) | Cod sursa (job #390080) | Cod sursa (job #161590) | Cod sursa (job #1702159) | Cod sursa (job #2671238)
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
#define Min(a, b) ((a) < (b) ? (a) : (b))
vector <int> adj[100005], dfn, low;
vector <vector <int> > C;
stack <pair <int, int> > stv;
void read_in(vector <int>* adj, int &n)
{
int i, x, y;
in >> n >> i;
for (; i > 0; i--) {
in >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
in.close();
}
void cache_bc(int x, int y)
{
vector <int> aux;
int tx, ty;
do {
tx = stv.top().first, ty = stv.top().second;
stv.pop();
aux.push_back(tx), aux.push_back(ty);
}
while (tx != x || ty != y);
C.push_back(aux);
}
void DF(int n, int fn, int number)
{
vector <int>::iterator i;
dfn[n] = low[n] = number;
for (i = adj[n].begin(); i != adj[n].end(); i++) {
if (*i == fn) continue ;
if (dfn[*i] == -1) {
stv.push( make_pair(n, *i) );
DF(*i, n, number + 1);
low[n] = Min(low[n], low[*i]);
if (low[*i] >= dfn[n])
cache_bc(n, *i);
}
else
low[n] = Min(low[n], dfn[*i]);
}
}
int main()
{
int n;
read_in(adj,n);
dfn.resize(n + 1);
dfn.assign(n + 1, -1);
low.resize(n + 1);
DF(1, 0, 0);
out << C.size() <<endl;
for(int i = 0; i < C.size(); i++)
{
sort(C[i].begin(), C[i].end());
C[i].erase( unique( C[i].begin(), C[i].end() ), C[i].end() );
for (int j = 0; j < C[i].size() ; j++)
out << C[i][j] << " ";
out << endl;
}
out.close();
return 0;
}