Pagini recente » Cod sursa (job #2245903) | Cod sursa (job #260419) | Cod sursa (job #2345001) | Cod sursa (job #2399826) | Cod sursa (job #3226647)
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector < int > v[100005];
int n, m, x, y, timp;
int disc[100005], low[100005];
int tata[100005];
bool viz[100005];
stack < pair < int, int > > st;
vector < int > biconex;
vector < vector < int > > components;
void read() {
f >> n >> m;
for (int i = 1; i <= m; i++) {
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void dfs_l(int nod) {
low[nod] = disc[nod] = ++timp;
for (auto k : v[nod]) {
if (disc[k] == 0) {
tata[k] = nod;
dfs_l(k);
low[nod] = min(low[nod], low[k]);
}
else if (k != tata[nod]) {
low[nod] = min(low[nod], low[k]);
}
}
}
void creare_biconex(int a, int b) {
biconex.clear();
int x = st.top().first, y = st.top().second;
while (x != a || y != b) {
biconex.push_back(y);
st.pop();
x = st.top().first; y = st.top().second;
}
st.pop();
biconex.push_back(y); biconex.push_back(x);
components.push_back(biconex);
}
bool punct_art(int x, int fiu) {
if (low[fiu] >= disc[x]) return 1;
return 0;
}
void dfs(int nod) {
viz[nod] = 1;
for (auto k : v[nod]) {
if (!viz[k]) {
st.push({ nod, k });
dfs(k);
if (punct_art(nod, k)) {
creare_biconex(nod, k);
}
}
}
}
void solve() {
for (int i = 1; i <= n; i++) {
if (disc[i] == 0) dfs_l(i);
}
for (int i = 1; i <= n; i++) {
if (!viz[i]) dfs(i);
}
}
void print() {
g << components.size() << '\n';
for (auto w : components) {
for (auto p : w) {
g << p << " ";
}
g << '\n';
}
}
int main() {
read();
solve();
print();
return 0;
}
/// O muchie este punte <=> în componenta biconexa nu mai sunt alte muchii
/// => luând toate componentele biconexe cu 2 noduri obținem PUNȚILE