Cod sursa(job #1919367)

Utilizator Julian.FMI Caluian Iulian Julian. Data 9 martie 2017 19:04:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#define nmax 100009
using namespace std;
list <int> g[nmax];
list <int> conex[nmax];
int nrc;
int d[nmax],low[nmax],t[nmax];
int timej;
int stf[nmax],sts[nmax],vf=-1;
vector<bool> viz(nmax,0);
void afisare(int u,int ut){


nrc++;
int n,nt,numb=0;
do{n=stf[vf];nt=sts[vf];
    if(!viz[nt]){viz[nt]=1;conex[nrc].push_back(nt);}
    if(!viz[n]) {viz[n]=1; conex[nrc].push_back(n);}
    vf--;numb++;
}while(n!=u || nt!=ut);

for(list<int>::iterator it=conex[nrc].begin();it!=conex[nrc].end();it++)
            viz[*it]=0;



}

void dfs(int x){
d[x]=++timej;
low[x]=timej;

for(list<int>::iterator it=g[x].begin();it!=g[x].end();++it){
    int u=*it;
    if(d[u]<d[x] && u!=t[x]){
        stf[++vf]=u; sts[vf]=x;
    }

    if(!d[u]){
        t[u]=x;
        dfs(u);
        low[x]=min(low[x],low[u]);
        if(low[u]>=d[x]){
            afisare(u,x);
        }
    }else if(u!=t[x]){low[x]=min(low[x],d[u]);}

}


}

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int main(){
int n,m,x,y,i;
    fin>>n>>m;
    while(m--)
    {fin>>x>>y;
     g[x].push_back(y);
     g[y].push_back(x);
    }

for(i=1;i<=n;i++)
    if(!d[i])
        {dfs(i);}

    fout<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
        {

            for(list<int>::iterator it=conex[i].begin();it!=conex[i].end();it++)
            fout<<*it<<' ';
        fout<<'\n';}
}