Pagini recente » Cod sursa (job #1942989) | Cod sursa (job #1374948) | Cod sursa (job #2881091) | Cod sursa (job #2046013) | Cod sursa (job #652344)
Cod sursa(job #652344)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100010
vector<int> G[MAXN], sol[MAXN];
int nodeL[MAXN], minL[MAXN], S[2][MAXN], s_top, sol_cnt;
void dfs(int n, int pn, int l){
nodeL[n]=minL[n]=l;
for(vector<int>::iterator i=G[n].begin(); i!=G[n].end(); i++){
if(nodeL[*i] == -1){
S[0][++s_top]=n; S[1][s_top]=*i;
dfs(*i, n, l+1);
minL[n]=min(minL[n], minL[*i]);
if(minL[*i] >= nodeL[n]){
int a, b;
sol_cnt++;
do {
sol[sol_cnt].push_back(a=S[0][s_top]);
sol[sol_cnt].push_back(b=S[1][s_top]);
s_top--;
} while(a != n || b != *i);
}
}
else if(*i != pn)
minL[n]=min(minL[n], minL[*i]);
}
}
int main(){
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int N, M, i, a, b, j;
scanf("%d%d", &N, &M);
for(i=1; i<=N; i++)
nodeL[i]=-1;
for(i=0; i<M; i++){
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
s_top=-1; sol_cnt=-1;
dfs(1, 0, 0);
printf("%d\n", sol_cnt+1);
for(i=0; i<=sol_cnt; i++){
sort(sol[i].begin(), sol[i].end());
printf("%d ", sol[i][0]);
for(j=1; j<sol[i].size(); j++)
if(sol[i][j] != sol[i][j-1])
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}