Cod sursa(job #1919339)

Utilizator Julian.FMI Caluian Iulian Julian. Data 9 martie 2017 18:55:09
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 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;

void afisare(int u,int ut){

cout<<"stiva:\n";
for(int i=0;i<=vf;i++)cout<<stf[i]<<' '<<sts[i]<<endl;
cout<<"gata\n";
cout<<u<<' '<<ut<<endl;

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

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++)
        {conex[i].sort();
         conex[i].unique();
            for(list<int>::iterator it=conex[i].begin();it!=conex[i].end();it++)
            fout<<*it<<' ';
        fout<<'\n';}
}