Pagini recente » Cod sursa (job #1091203) | Cod sursa (job #1975728) | Cod sursa (job #514160) | Cod sursa (job #511002) | Cod sursa (job #2666023)
#include<fstream>
#include<vector>
#include<stack>
#define NMAX 100001
#define DEFAULT_DISCOVERY_TIMES -1
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> adjList[NMAX];
int discoveryTimes[NMAX], low[NMAX];
stack<pair<int, int>> pairs;
vector<vector<int>> results;
bool isDiscovered(int node) {
return discoveryTimes[node] != DEFAULT_DISCOVERY_TIMES;
}
void biconex(int lowX, int lowY) {
vector<int> temp;
int x, y;
do {
x = pairs.top().first;
y = pairs.top().second;
pairs.pop();
temp.push_back(y);
} while (lowX != x && lowY != y);
temp.push_back(x);
results.push_back(temp);
}
void dfs(int startNode, int parent, int no) {
discoveryTimes[startNode] = low[startNode] = no;
for (const auto& node : adjList[startNode]) {
if (node != parent) {
if (!isDiscovered(node)) {
pairs.push(make_pair(startNode, node));
dfs(node, startNode, no + 1);
if (low[startNode] > low[node]) {
low[startNode] = low[node];
}
if (low[node] >= discoveryTimes[startNode]) {
biconex(startNode, node);
}
}
else {
low[startNode] = min(low[startNode], discoveryTimes[node]);
}
}
}
}
int main() {
int N, M;
in >> N >> M;
for (int i = 0; i < M; ++i) {
int startNode, endNode;
in >> startNode >> endNode;
adjList[startNode].push_back(endNode);
adjList[endNode].push_back(startNode);
}
for (int i = 1; i <= N; i++) {
discoveryTimes[i] = DEFAULT_DISCOVERY_TIMES;
}
dfs(1, 0, 0);
out << results.size() << '\n';
for (const auto& result : results) {
for (const auto& node : result) {
out << node << ' ';
}
out << '\n';
}
return 0;
}