Pagini recente » Cod sursa (job #1186691) | Cod sursa (job #1545359) | Cod sursa (job #45158) | Cod sursa (job #2714862) | Cod sursa (job #2139080)
#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 saveBcc(int _x, int _y) {
vector<int> currBcc;
int x, y;
do {
tie(x, y) = tarjanEdges.top();
tarjanEdges.pop();
currBcc.push_back(x);
currBcc.push_back(y);
} while (x != _x || y != _y);
BCC.push_back(currBcc);
}
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])
saveBcc(node, it);
}
}
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) {
sort(i.begin(), i.end());
i.erase(unique(i.begin(), i.end()), i.end());
for (auto j: i)
cout << j << ' ';
cout << '\n';
}
return 0;
}