Pagini recente » Cod sursa (job #1426425) | Cod sursa (job #1937491) | Cod sursa (job #691315) | Cod sursa (job #3255732) | Cod sursa (job #2139077)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100010;
const int inf = 0x3f3f3f3f;
int N, M;
int currTime = 0, currBcc = 0;
int discoverTime[NMAX], lowLink[NMAX];
vector<int> G[NMAX];
vector<int> BCC[NMAX];
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]) {
int x, y;
do {
tie(x, y) = tarjanEdges.top();
tarjanEdges.pop();
BCC[currBcc].push_back(x);
BCC[currBcc].push_back(y);
} while (x != node || y != it);
++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 << currBcc << '\n';
for (int i = 0; i < currBcc; ++i) {
sort(BCC[i].begin(), BCC[i].end());
BCC[i].erase(unique(BCC[i].begin(), BCC[i].end()), BCC[i].end());
for (auto j: BCC[i])
cout << j << ' ';
cout << '\n';
}
return 0;
}