Pagini recente » Cod sursa (job #888696) | Cod sursa (job #1770713) | Cod sursa (job #2843902) | Cod sursa (job #1077532) | Cod sursa (job #2139093)
#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;
vector<pair<int, int>> tarjanEdges;
void tarjanDFS(int node, int from, int currTime) {
discoverTime[node] = lowLink[node] = currTime;
for (int it: G[node]) {
if (it == from)
continue;
if (discoverTime[it] != -1) {
lowLink[node] = min(lowLink[node], discoverTime[it]);
continue;
}
tarjanEdges.push_back({node, it});
tarjanDFS(it, node, currTime + 1);
lowLink[node] = min(lowLink[node], lowLink[it]);
if (lowLink[it] >= discoverTime[node]) {
vector<int> currBcc;
int x, y;
do {
tie(x, y) = tarjanEdges.back();
tarjanEdges.pop_back();
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);
cin >> N >> M;
while (M--) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
tarjanDFS(1, 0, 0);
cout << BCC.size() << '\n';
for (auto i: BCC) {
for (auto j: i)
cout << j << ' ';
cout << '\n';
}
return 0;
}