Cod sursa(job #2526383)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 18 ianuarie 2020 15:46:58
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <stack>
#define NM 100003
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,i,j,x,y,time,m,nr;
int vis[NM],t[NM],parent[NM],fr[NM];
vector < int > a[NM],rasp[NM];
stack < int > q;
void rec(int nod,int prnt){
  bool isnod=false;
  int child=0;
  vis[nod]=t[nod]=++time;
  fr[nod]=1;
  parent[nod]=prnt;
  q.push(nod);
  for(int i=0;i<a[nod].size();i++){
     int x=a[nod][i];
     if(prnt==x) continue;
       else
     if(fr[x]==0){
          child++;
          rec(x,nod);
          t[nod]=min(t[x],t[nod]);
          if(vis[nod]<=t[x]){
            nr++;
            while(q.top()!=x){
                rasp[nr].push_back(q.top());
                q.pop();
            }
            rasp[nr].push_back(nod);
            rasp[nr].push_back(x);
            q.pop();
          }
       }
       else t[nod]=min(vis[x],t[nod]);
  }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    rec(1,-1);
    g<<nr<<'\n';
    for(i=1;i<=nr;i++){
        for(j=0;j<rasp[i].size();j++)
            g<<rasp[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}