Pagini recente » Cod sursa (job #3266343) | Cod sursa (job #2603234) | Cod sursa (job #122243) | Borderou de evaluare (job #382912) | Cod sursa (job #2668116)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 100005;
const int INF = 1000000000;
vector<int> muchii[NMAX];
vector<int> biconexe[NMAX];
int viz[NMAX];
int nivel[NMAX];
int inaltime[NMAX];
bool critic[NMAX];
int dfs_sons[NMAX];
int num_bic;
void dfs_critic(int nod) {
viz[nod] = 1;
for (const auto &vec : muchii[nod]) {
if (!viz[vec]) {
nivel[vec] = nivel[nod] + 1;
dfs_sons[nod]++;
dfs_critic(vec);
if (inaltime[vec] >= nivel[nod]) {
critic[nod] = true;
}
inaltime[nod] = min(inaltime[nod], inaltime[vec]);
}
else {
inaltime[nod] = min(inaltime[nod], nivel[vec]);
}
}
}
void dfs_biconexe(int nod, int index);
void split_biconexe(int nod) {
viz[nod] = 1;
for (auto &vec : muchii[nod]) {
if (viz[vec]) {
continue;
}
biconexe[++num_bic].push_back(nod);
if (critic[vec]) {
biconexe[num_bic].push_back(vec);
split_biconexe(vec);
}
else {
dfs_biconexe(vec, num_bic);
}
}
}
void dfs_biconexe(int nod, int index) {
viz[nod] = 1;
biconexe[index].push_back(nod);
for (auto &vec : muchii[nod]) {
if (viz[vec]) {
continue;
}
if (critic[vec]) {
biconexe[index].push_back(vec);
split_biconexe(vec);
}
else {
dfs_biconexe(vec, index);
}
}
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,a,b;
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> a >> b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
inaltime[i] = INF;
}
dfs_critic(1);
critic[1] = (dfs_sons[1] > 1);
for (auto &v : viz) {
v = 0;
}
for(int i = 1; i <= n; i++) {
if(critic[i]) {
split_biconexe(i);
break;
}
}
fout << num_bic << "\n";
for (int i = 1; i <= num_bic; i++) {
for (auto &elem : biconexe[i]) {
fout << elem << " ";
}
fout << "\n";
}
return 0;
}