Pagini recente » Cod sursa (job #2208382) | Cod sursa (job #1776502) | Cod sursa (job #3323887) | Cod sursa (job #1882583) | Cod sursa (job #3318728)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
#define MAXN 100005
// zona de declarare
int n, m;
vector <int> adj[MAXN]; // adiacenta
int niv[MAXN+1], low[MAXN+1]; // niv low
vector <vector <int> > C; // matricea rezultat cu ciclurile
stack <pair <int, int> > stk; // stackul de noduri/muchii in componenta biconexa
void extract(const int x, const int y) // introducerea componentei in rezultat
{
vector <int> con; int tx, ty;
do {
tx = stk.top().first, ty = stk.top().second; // iau cate o muchie
stk.pop();
con.push_back(tx), con.push_back(ty);
}
while (tx != x || ty != y);
C.push_back(con); // muchie cu muchie
}
void DF(const int n, const int fn)
{
niv[n] = low[n] = niv[fn]+1;
for (auto it : adj[n]) {
if (it == fn) continue ; // se repeta e ciclu cvcv
if (niv[it] == -1) { // nevizitat
stk.push( make_pair(n, it) ); // imi pune muchia pe stack
DF(it, n);
low[n] = min(low[n], low[it]); // actualizam low ul
if (low[it] >= niv[n])
extract(n, it); // capatul componentei biconexe
}
else
low[n] = min(low[n], niv[it]);
}
}
int main()
{
// citire si initializare
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 0; i <= n; i++) {
niv[i] = low[i] = -1;
}
// apelarea algoritmului
DF(1, 0);
// afisarea de date
fout << C.size() << "\n";
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()); // sterge duplicatele
for (int j = 0; j < C[i].size(); ++ j)
fout << C[i][j] << " ";
fout << "\n";
}
return 0;
}