Pagini recente » Cod sursa (job #3296861) | Cod sursa (job #2642419) | Cod sursa (job #2252351) | Istoria paginii runda/arhiva-utcn | Cod sursa (job #2659157)
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M, root;
int minNiv[NMAX], niv[NMAX];
vector<vector<int>> gr, comp;
stack<pair<int, int>> st;
void read() {
fin >> N >> M;
int x, y;
gr.resize(N + 1);
for (int i = 0; i < M; ++i) {
fin >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
}
void addComponent(int x, int y) {
pair<int, int> top;
vector<int> v;
do {
top = st.top();
st.pop();
v.push_back(top.second);
}while(!st.empty() && (top.first != x || top.second != y));
v.push_back(top.first);
comp.push_back(v);
}
void addRootComponent(int x) {
vector<int> v;
pair<int, int> top;
do {
top = st.top();
st.pop();
v.push_back(top.second);
}while(!st.empty() && (top.first != x && top.second != x));
v.push_back(top.first);
comp.push_back(v);
}
void DFS(int node, int previousNode) {
int nrF = 0;
niv[node] = niv[previousNode] + 1;
minNiv[node] = niv[node];
for (int i : gr[node]) {
if (niv[i] == 0) {
++nrF;
st.emplace(node, i);
DFS(i, node);
minNiv[node] = min(minNiv[node], minNiv[i]);
if (minNiv[i] >= niv[node] && node != root) {
addComponent(node, i);
}
}
else if(i != previousNode) {
minNiv[node] = min(minNiv[node], niv[i]);
}
}
if (nrF > 1 && node == root) {
addRootComponent(root);
}
}
int main()
{
read();
for (int i = 1; i <= N; ++i) {
if (niv[i] == 0) {
root = i;
DFS(i, 0);
if (!st.empty()) {
vector<int> v;
pair<int, int> top;
while (!st.empty()) {
top = st.top();
st.pop();
v.push_back(top.second);
}
v.push_back(top.first);
comp.push_back(v);
}
}
}
fout << comp.size() << "\n";
for (int i = 0; i < comp.size(); ++i) {
for (int j = comp[i].size() - 1; j >= 0; --j) {
fout << comp[i][j] << " ";
}
fout << "\n";
}
return 0;
}