Cod sursa(job #2125118)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 7 februarie 2018 23:33:34
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct op{
    int x,y;
}st[100001];
int N,M,x,y,nr,nrsol,low[100001];
bool n[100001];
vector <int> G[100001],sol[100001];
void DFS(int nod,int nivel,int parinte){
    n[nod]=1,low[nod]=nivel;
    for(int i=0;i<(int)G[nod].size();++i)
        if(G[nod][i]!=parinte){
            bool ok=false;
            if(n[G[nod][i]]==false){
               ++nr,st[nr].x=nod,st[nr].y=G[nod][i],ok=true;
               DFS(G[nod][i],nivel+1,nod);
            }
            low[nod]=min(low[nod],low[G[nod][i]]);
            if(ok==true&&low[G[nod][i]]>=nivel){
                sol[++nrsol].push_back(nod);
                while(st[nr].x!=nod){
                    sol[nrsol].push_back(st[nr].y);
                    --nr;
                }
                sol[nrsol].push_back(st[nr].y);
                --nr;
            }
        }
}
int main()
{
    f>>N>>M;
    while(M--){
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1,1,0);
    g<<nrsol<<'\n';
    for(int i=1;i<=nrsol;++i){
        for(int j=0;j<(int)sol[i].size();++j)g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}