Pagini recente » Cod sursa (job #1807057) | Cod sursa (job #266292) | Cod sursa (job #1481903) | Cod sursa (job #1833887) | Cod sursa (job #1923594)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define Nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> bc[Nmax];
stack< pair<int,int> > S;
int nrbc = 0;
struct el{int first, second;};
void citire(int &n, vector<int> G[]) {
int m, a, b;
f >> n >> m;
while(m--) {
f >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
}
void bicon(int nod, int fiu){
int x, y;
nrbc++;
do {
x = S.top().first;
y = S.top().second;
S.pop();
bc[nrbc].push_back(y);
} while (x != nod && y != fiu);
bc[nrbc].push_back(x);
}
void getCritical(int nod, vector<int> G[], int H[], int Niv[], bitset<Nmax> &isCritic,
bitset<Nmax> &isUsed) {
isUsed[nod] = 1;
H[nod] = Niv[nod];
for(int i = 0; i < G[nod].size(); ++i) {
int j = G[nod][i];
if(!isUsed[j]) {
S.push(make_pair(nod, j));
Niv[j] = Niv[nod] + 1;
getCritical(j, G, H, Niv, isCritic, isUsed);
H[nod] = min(H[nod], H[j]);
if(H[j] >= Niv[nod]) {
// g << nod << " * " << j << '\n';
bicon(nod, j);
isCritic[nod] = 1;
}
}
else if (Niv[j] < Niv[nod] - 1)
H[nod] = min(H[nod], Niv[j]);
}
}
void adaug(vector<int> lista[], int nod, int j) {
for(int i = 0; i < lista[nod].size(); ++i)
if(lista[nod][i] == j) return;
lista[nod].push_back(j);
}
int main()
{
int N, H[Nmax], Niv[Nmax];
vector<int> G[Nmax];
bitset<Nmax> isUsed;
bitset<Nmax> isCritic;
isUsed.reset();
isCritic.reset();
citire(N, G);
//pregatim proc
for(int i = 0; i < Nmax - 10; ++i)
H[i] = Niv[i] = 0;
getCritical(1 , G, H, Niv, isCritic, isUsed);
// Puncte critice,
//Verificam daca 1 este critic
int ok = 0;
for(int i = 1; i <= N; ++i)
if(Niv[i] == 1)
ok++;
if(ok > 1)
isCritic[1] = 1;
else
isCritic[1] = 0;
g << nrbc << '\n';
for(int i = 1; i <= nrbc; ++i) {
for(int j = 0; j < bc[i].size(); ++j)
g << bc[i][j] << " ";
g << '\n';
}
return 0;
}