Pagini recente » Cod sursa (job #901631) | Cod sursa (job #232450) | Cod sursa (job #3190466) | Cod sursa (job #448258) | Cod sursa (job #2569348)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100505;
int N, M, parent[NMAX];
vector<int> graph[NMAX];
int low[NMAX], lvl[NMAX];
bool visited[NMAX];
stack<pair<int, int>> edges;
vector<vector<int>> comps;
int nodeToComp[NMAX];
void read() {
scanf("%d%d", &N, &M);
int x, y;
for (int edgeIdx = 0; edgeIdx < M; edgeIdx++) {
scanf("%d%d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
}
void addNodeToLatestComp(int node, int compsNo, vector<int>& newComp) {
if (nodeToComp[node] != compsNo) {
nodeToComp[node] = compsNo;
newComp.push_back(node);
}
}
void addEdgeToLatestComp(pair<int, int>& edge, int compsNo, vector<int>& newComp) {
addNodeToLatestComp(edge.first, compsNo, newComp);
addNodeToLatestComp(edge.second, compsNo, newComp);
}
void dfs(int node) {
visited[node] = true;
low[node] = lvl[node];
for (auto& neighbour : graph[node]) {
if (!visited[neighbour]) {
parent[neighbour] = node;
edges.push({node, neighbour});
lvl[neighbour] = lvl[node] + 1;
dfs(neighbour);
if (low[neighbour] >= lvl[node]) {
vector<int> newComp;
while (!edges.empty()) {
pair<int, int> edge = edges.top();
edges.pop();
addEdgeToLatestComp(edge, (int) comps.size() + 1, newComp);
if (edge.first == node && edge.second == neighbour) {
break;
}
}
comps.push_back(newComp);
}
low[node] = min(low[node], low[neighbour]);
} else if (parent[node] != neighbour) {
low[node] = min(low[node], low[neighbour]);
}
}
}
void solve() {
for (int node = 1; node <= N; node++) {
if (!visited[node]) {
dfs(node);
}
}
printf("%d\n", (int) comps.size());
for (auto comp : comps) {
for (auto node : comp) {
printf("%d ", node);
}
printf("\n");
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
read();
solve();
return 0;
}