Pagini recente » Cod sursa (job #2865473) | Cod sursa (job #872234) | Cod sursa (job #2735635) | Cod sursa (job #2928467) | Cod sursa (job #296180)
Cod sursa(job #296180)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 100010
int n, m, i, p, q, k, sol;
int fol[MAX_N], niv[MAX_N], tata[MAX_N], c[MAX_N];
int stiv[MAX_N][2];
vector <int> A[MAX_N], S[MAX_N];
void cit() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d %d", &p, &q);
A[p].push_back(q);
A[q].push_back(p);
}
}
void dfs(int nod) {
fol[nod] = 1;
//c[i] = nivelul minim la care pot ajunge din subarborele lui i
c[nod] = niv[nod];
int len = A[nod].size();
for (int i = 0; i < len; i++) {
int son = A[nod][i];
if (!fol[son]) {
tata[son] = nod;
niv[son] = niv[nod] + 1;
stiv[++k][0] = nod;
stiv[k][1] = son;
dfs(son);
if (c[nod] > c[son]) c[nod] = c[son];
//am gasit o componenta biconexa
if (c[son] >= niv[nod]) {
sol++;
while (!(stiv[k][0] == nod && stiv[k][1] == son)) {
S[sol].push_back(stiv[k][0]);
S[sol].push_back(stiv[k][1]);
k--;
}
S[sol].push_back(stiv[k][0]);
S[sol].push_back(stiv[k][1]);
k--;
}
}
else if (tata[nod] != son && niv[son] < niv[nod]) {
if (c[nod] > niv[son]) c[nod] = niv[son];
stiv[++k][0] = nod;
stiv[k][1] = son;
}
}
}
void write() {
printf("%d\n", sol);
for (i = 1; i <= sol; i++) {
sort(S[i].begin(), S[i].end());
int len = S[i].size();
for (int j = 0; j < len; j++)
if ((j < len - 1 && S[i][j] != S[i][j + 1]) || j == len - 1)
printf("%d ", S[i][j]);
printf("\n");
}
}
int main() {
cit();
//fac arborele DF al grafului
dfs(1);
write();
return 0;
}