Cod sursa(job #2472110)

Utilizator Leonard123Mirt Leonard Leonard123 Data 12 octombrie 2019 08:29:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 100005
vector <int> v[maxn],c[maxn];
vector <pair<int,int> >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){
  pair<int, int> x1;
  cnt++;
  while(x!=x1.first||y!=x1.second){
    x1=stk.back(); stk.pop_back();
    c[cnt].push_back(x1.first);
    c[cnt].push_back(x1.second);
  }
}

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(make_pair(n,*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],dfn[*it]);
  }
}

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

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