Pagini recente » Cod sursa (job #2789311) | Cod sursa (job #1833228) | Cod sursa (job #808708) | Cod sursa (job #773881) | Cod sursa (job #1378787)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int kNMax = 100010;
int n, nr_sol, nivel[kNMax], adn[kNMax];
stack<pair<int,int> > Stack;
vector<int> G[kNMax], sol[kNMax];
void Citire() {
ifstream in("biconex.in");
int m, x, y;
in >> n >> m;
for (int i = 1; i <= m; ++i) {
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
in.close();
}
void Dfs(int nod, int tata) {
nivel[nod] = nivel[tata] + 1;
adn[nod] = nivel[nod];
for (int i = 0; i < G[nod].size(); ++i) {
int vecin = G[nod][i];
if (vecin != tata) {
if (nivel[vecin] == 0) {
Stack.push(make_pair(nod, vecin));
Dfs(vecin, nod);
if (adn[vecin] >= nivel[nod]) {
int x = Stack.top().first;
int y = Stack.top().second;
Stack.pop();
sol[++nr_sol].push_back(y);
while (nod != x && vecin != y) {
x = Stack.top().first;
y = Stack.top().second;
Stack.pop();
sol[nr_sol].push_back(y);
}
sol[nr_sol].push_back(x);
}
}
adn[nod] = min(adn[nod], adn[vecin]);
}
}
}
void Afisare() {
ofstream out("biconex.out");
out << nr_sol << '\n';
for (int i = 1; i <= nr_sol; ++i) {
for (int j = 0; j < sol[i].size(); ++j)
out << sol[i][j] << ' ';
out << '\n';
}
out.close();
}
int main() {
Citire();
Dfs(1, 0);
Afisare();
return 0;
}