Pagini recente » Cod sursa (job #1631068) | Cod sursa (job #51477) | Cod sursa (job #1767432) | Cod sursa (job #3168993) | Cod sursa (job #2139074)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100010;
const int inf = 0x3f3f3f3f;
int N, M;
int currTime = 0;
int discoverTime[NMAX], lowLink[NMAX];
vector<int> G[NMAX];
vector<vector<int>> BCC;
stack<pair<int, int>> tarjanEdges;
void tarjanDFS(int node) {
discoverTime[node] = currTime++;
for (int it: G[node]) {
if (discoverTime[it] != -1) {
lowLink[node] = min(lowLink[node], discoverTime[it]);
continue;
}
tarjanEdges.push({node, it});
tarjanDFS(it);
lowLink[node] = min(lowLink[node], lowLink[it]);
if (lowLink[it] >= discoverTime[node]) {
vector<int> currBcc;
int x, y;
do {
tie(x, y) = tarjanEdges.top();
tarjanEdges.pop();
currBcc.push_back(x);
currBcc.push_back(y);
} while (x != node || y != it);
sort(currBcc.begin(), currBcc.end());
currBcc.erase(unique(currBcc.begin(), currBcc.end()), currBcc.end());
BCC.push_back(currBcc);
}
}
}
int main() {
assert(freopen("biconex.in", "r", stdin));
assert(freopen("biconex.out", "w", stdout));
memset(discoverTime, -1, sizeof discoverTime);
memset(lowLink, inf, sizeof lowLink);
cin >> N >> M;
while (M--) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
tarjanDFS(1);
cout << BCC.size() << '\n';
for (auto i: BCC) {
for (auto j: i)
cout << j << ' ';
cout << '\n';
}
return 0;
}