Pagini recente » Cod sursa (job #357256) | Cod sursa (job #1400103) | Cod sursa (job #63210) | Cod sursa (job #2737387) | Cod sursa (job #530296)
Cod sursa(job #530296)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 100010
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); ++i)
vector <int> G[NMAX], SOL[NMAX];
int viz[NMAX];
int L[NMAX], c[NMAX];
int st[NMAX][2];
int tata[NMAX];
int n, m, k;
int sol;
void dfs(int x) {
viz[x] = 1;
c[x] = L[x];
FOR(i, G[x])
if(!viz[*i]){
L[*i] = L[x] + 1;
tata[*i] = x;
st[++k][0] = x;
st[k][1] = *i;
dfs(*i);
if(c[*i] < c[x]) c[x] = c[*i];
if(c[*i] >= L[x]){
sol++;
while( !( st[k][0] == x && st[k][1] == *i)){
SOL[sol].push_back(st[k][1]);
SOL[sol].push_back(st[k][0]);
k--;
}
SOL[sol].push_back(st[k][1]);
SOL[sol].push_back(st[k][0]);
k--;
}
}
else if(tata[x] != *i && L[*i] < L[x]){
if(c[x] > L[*i]) c[x] = L[*i];
st[++k][0] = x;
st[k][1] = *i;
}
}
int main(){
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i){
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
printf("%d\n", sol);
for(int i = 1; i <= sol; ++i) {
sort(SOL[i].begin(), SOL[i].end());
printf("%d", *SOL[i].begin());
for(unsigned int j = 1; j < SOL[i].size(); ++j)
if(SOL[i][j] != SOL[i][j-1]) printf(" %d", SOL[i][j]);
printf("\n");
}
return 0;
}