Pagini recente » Cod sursa (job #144486) | Cod sursa (job #115574) | Cod sursa (job #1805641) | Cod sursa (job #317824) | Cod sursa (job #2696618)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
const int NMAX=100005;
vector<int> graph[NMAX];
vector<int> discover, low, parent;
vector<int> biconexe[NMAX];
struct muchie
{
int nod1, nod2;
};
stack<muchie> st;
int timp, n, nr;
void componenta(int x, int y) {
int i, j;
nr++;
do {
i = st.top().nod1;
j = st.top().nod2;
st.pop();
biconexe[nr].push_back(j);
} while(i != x && j != y);
biconexe[nr].push_back(x);
}
void dfs(int nod) {
muchie aux{};
timp++;
discover[nod] = low[nod] = timp;
for(auto &fiu : graph[nod]) {
if(parent[fiu] != nod) {
if(!discover[fiu]) {
aux.nod1 = nod;
aux.nod2 = fiu;
st.push(aux);
parent[fiu] = nod;
dfs(fiu);
if(low[fiu] >= discover[nod]) {
componenta(nod, fiu);
}
low[nod] = min(low[nod], low[fiu]);
}
else {
low[nod] = min(low[nod], discover[fiu]);
}
}
}
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int m, u, v;
fin >> n >> m;
for(int i = 1; i <= m; i++) {
fin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
parent.resize(n+1, 0);
low.resize(n+1, 0);
discover.resize(n+1, 0);
for(int i = 1; i <= n; i++) {
if(!discover[i])
dfs(i);
}
fout << nr << "\n";
for(int i = 1; i <= nr; i++) {
for(auto &elem : biconexe[i]) {
fout << elem << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}