Pagini recente » Borderou de evaluare (job #324775) | Cod sursa (job #541991) | Cod sursa (job #1706649)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nMax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
vector <int> lvl;
vector <int> low;
vector <int> graph[nMax];
vector < vector <int> > CBlist;
stack < pair <int, int> > st;
void citire() {
int x, y;
f >> n >> m;
for (int i = 0; i < m; i++) {
f >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
}
int getMin (int x, int y) {
if (x < y) return x;
else return y;
}
void compBiconexe(int x, int y) {
vector <int> currCompB;
pair <int, int> current;
do {
current = st.top();
st.pop();
currCompB.push_back(current.second);
}
while (current.first != x && current.second != y);
currCompB.push_back(current.first);
CBlist.push_back(currCompB);
}
void DFS(int x) {
int level, i;
low[x] = lvl[x];
for (i = 0; i < graph[x].size(); i++) {
level = graph[x][i];
if (!lvl[level]) {
lvl[level] = lvl[x] + 1;
st.push(make_pair(x, level));
DFS(level);
low[x] = getMin(low[x], low[level]);
if (lvl[x] <= low[level])
compBiconexe(x, level);
}
else low[x] = getMin(low[x], lvl[level]);
}
}
int main() {
citire();
lvl.resize(n + 1, 0);
low.resize(n + 1, 0);
for (int i = 1; i <= n; i++)
if (!lvl[i]) {
lvl[i] = 1;
DFS(i);
}
g << CBlist.size() << endl;
for (int i = 0; i < CBlist.size(); i++) {
for (int j = 0; j < CBlist[i].size(); j++)
g << CBlist[i][j] << " ";
g << endl;
}
return 0;
}