Pagini recente » Cod sursa (job #2380628) | Cod sursa (job #2619602) | Cod sursa (job #672140) | Cod sursa (job #2169054) | Cod sursa (job #2667400)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m, x, y, vizitat[100001], low[100001], vf;
vector <int> G[100001], aux;
vector <vector <int>> rez;
pair <int, int> stiva[200001];
void citire() {
f >> n >> m;
for(int i = 1; i <= m; i++) {
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void biconex(int lx, int ly) {
aux.clear();
x = stiva[vf].first;
y = stiva[vf].second;
vf--;
aux.push_back(y);
while(lx != x && ly != y){
x = stiva[vf].first;
y = stiva[vf].second;
vf--;
aux.push_back(y);
}
aux.push_back(x);
rez.push_back(aux);
}
void DFS(int node, int tata, int nr) {
vizitat[node] = nr;
low[node] = nr;
for(int i = 0; i < G[node].size(); i++) {
if(G[node][i] != tata) {
if(vizitat[G[node][i]] == -1) {
vf++;
stiva[vf] = make_pair(node, G[node][i]);
DFS(G[node][i], node, nr + 1);
low[node] = min(low[node], low[G[node][i]]);
if(low[G[node][i]] >= vizitat[node])
biconex(node, G[node][i]);
}else {
low[node] = min(low[node], vizitat[G[node][i]]);
}
}
}
}
int main() {
citire();
memset(vizitat, -1, sizeof(vizitat));
DFS(1, 0, 0);
g << rez.size() << '\n';
for(int i = 0; i < rez.size(); i++) {
for(int j = 0; j < rez[i].size(); j++)
g << rez[i][j] << ' ';
g << '\n';
}
}