Cod sursa(job #652344)

Utilizator Smaug-Andrei C. Smaug- Data 24 decembrie 2011 02:06:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#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;

}