Pagini recente » Cod sursa (job #1231624) | Cod sursa (job #1974818) | Cod sursa (job #3282732) | Cod sursa (job #1958729) | Cod sursa (job #553869)
Cod sursa(job #553869)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 100010
int n, m, k, t;
int use[MAX_N], depth[MAX_N], up[MAX_N];
int stack[2][MAX_N];
vector <int> A[MAX_N], S[MAX_N];
void read() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int p, q;
scanf("%d %d", &p, &q);
A[p].push_back(q);
A[q].push_back(p);
}
}
void dfs(int vertex) {
use[vertex] = 1;
up[vertex] = depth[vertex];
for (vector <int>::iterator it = A[vertex].begin(); it != A[vertex].end(); ++it)
if (use[*it] == 0) {
depth[*it] = depth[vertex] + 1;
stack[0][++t] = vertex;
stack[1][t] = *it;
dfs(*it);
if (up[*it] >= depth[vertex]) { //am gasit o componenta biconexa
k++;
while (!(stack[0][t] == vertex && stack[1][t] == *it)) {
S[k].push_back(stack[1][t]);
t--;
}
S[k].push_back(vertex);
S[k].push_back(*it);
t--;
}
up[vertex] = min(up[vertex], up[*it]);
}
else
up[vertex] = min(up[vertex], depth[*it]);
}
void write() {
printf("%d\n", k);
for (int i = 1; i <= k; i++) {
for (vector <int>::iterator it = S[i].begin(); it != S[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
}
int main() {
read();
dfs(1);
write();
return 0;
}