Cod sursa(job #904450)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 4 martie 2013 14:01:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include<cstdio>
#include<cassert>
#include<cstring>

#include<algorithm>
#include<vector>
#include<queue>

#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m, level, vis[100005], dp[100005], lvl[100005], bad_edg[200005];
vector<pair<int, int> > be, graph[100005];

void dfs_edg_crit(int x, int v, int dad){
  ++level;
  lvl[x] = level;
  dp[x] = 9000001;
  vis[x] = 1;

  for(int i = 0; i < graph[x].size(); ++i)
    if(!vis[graph[x][i].f]){
      dfs_edg_crit(graph[x][i].f, graph[x][i].s, x);
      dp[x] = min(dp[x], dp[graph[x][i].f]);
    }
    else if(graph[x][i].s != v)
      dp[x] = min(dp[x], lvl[graph[x][i].f]);

  if(dp[x] >= lvl[x]){
    bad_edg[v] = 1;
    be.push_back(mp(x, dad));
  }

  --level;
}

int nr_comp, comp[100005];
vector<int> lel[100005];

void dfs(int x){
  lel[nr_comp].push_back(x);
  vis[x] = 1;
  comp[x] = nr_comp;

  for(int i = 0; i < graph[x].size(); ++i)
    if(!bad_edg[graph[x][i].s] && !vis[graph[x][i].f])
      dfs(graph[x][i].f);
}

int dad[100005];
vector<int> arb[100005];

void read(){
 // assert(freopen("critice2.in", "r", stdin));

  scanf("%d%d", &n, &m);

  for(int i = 1; i <= m; ++i){
    int x, y;
    scanf("%d%d", &x, &y);
    graph[x].pb(mp(y, i));
    graph[y].pb(mp(x, i));
  }

  dfs_edg_crit(1, 0, 0);
  be.pop_back();

  memset(vis, 0, sizeof(vis));

  for(int i = 1; i <= n; ++i)
    if(!vis[i]){
      ++nr_comp;
      dfs(i);
      if(lel[nr_comp].size() < 2){
        --nr_comp;
        lel[nr_comp + 1].clear();
      }
    }

  for(int i = 0; i < be.size(); ++i){
    arb[comp[be[i].f]].pb(comp[be[i].s]);
    arb[comp[be[i].s]].pb(comp[be[i].f]);
    ++nr_comp;
    lel[nr_comp].push_back(be[i].f);
    lel[nr_comp].push_back(be[i].s);
  }

}

double ans;

void solve(){

}

void write(){
  //assert(freopen("critice2.out", "w", stdout));

//  printf("%lf", ans);

  printf("%d\n", nr_comp);

  for(int i = 1; i <= nr_comp; ++i){
    for(int j = 0; j < lel[i].size(); ++j)
      printf("%d ", lel[i][j]);
    printf("\n");
  }

}

int main(){
  assert(freopen("biconex.out", "w", stdout));
  assert(freopen("biconex.in", "r", stdin));
  read();
  solve();
  write();

  return 0;
}