Cod sursa(job #2472107)

Utilizator Leonard123Mirt Leonard Leonard123 Data 12 octombrie 2019 08:11:56
Problema Componente biconexe Scor 54
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<vector>
using namespace std;
#define maxn 100005
vector <int> v[maxn],c[maxn],stk;
int low[maxn],dfn[maxn],n,m,cnt;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

void read(){
  cin>>n>>m;
  int x,y;
  while(m){
    cin>>x>>y;
    v[x].push_back(y);
    v[y].push_back(x);
    m--;
  }
}

void clear_stk(int x, int y){
  int x1,y1;
  cnt++;
  y1=stk.back(); stk.pop_back();
  x1=stk.back(); stk.pop_back();
  c[cnt].push_back(y1);
  c[cnt].push_back(x1);
  while(x!=x1||y!=y1){
    y1=stk.back(); stk.pop_back();
    x1=stk.back(); stk.pop_back();
    if(y1!=c[cnt].back())
      c[cnt].push_back(y1);
    c[cnt].push_back(x1);
  }
}

void dfs(int n, int fn, int number){
  vector<int>::iterator it;
  dfn[n]=low[n]=number;
  for(it=v[n].begin(); it!=v[n].end(); it++){
      if(*it==fn)
        continue;
      else if(!dfn[*it]){
        stk.push_back(n);
        stk.push_back(*it);
        dfs(*it, n, ++number);
        low[n]=min(low[*it],low[n]);
        if(dfn[n]<=low[*it])
          clear_stk(n,*it);
      }
      else
        low[n]=min(low[n],low[*it]);
  }
}

void solve(){
  dfs(1,-1,1);
  cout<<cnt<<'\n';
  for(int i=1; i<=cnt; i++){
    for(vector <int>::iterator it=c[i].end()-1; it>=c[i].begin(); it--)
        cout<<*it<<' ';
    cout<<'\n';
  }
}

int main(){
  read();
  solve();
  return 0;
}