Cod sursa(job #1966576)

Utilizator geo_furduifurdui geo geo_furdui Data 15 aprilie 2017 13:13:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include<vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> t[100100],sol[100100];
int n,m,nr;
int st[100100];
int nivel[100100],vf;
int up[100100],used[100100];
void read ()
{ int a,b;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        t[a].push_back(b);
        t[b].push_back(a);
    }
    nivel[1]=1;
}
void dfs (int nod,int dad)
{
    if(used[nod]!=0) return;
    used[nod]=1;
    st[++vf]=nod;
    nivel[nod]=nivel[dad]+1;
    up[nod]=nivel[nod];
    for(vector <int> :: iterator i=t[nod].begin(); i!=t[nod].end(); i++)
    {
        if(used[*i]==1)
        {
            if(*i!=dad) up[nod]=min(up[nod],nivel[*i]);
        }
        else
        {
            dfs(*i,nod);
            up[nod]=min(up[nod],up[*i]);
            if(up[*i]>=nivel[nod])
            {
                nr++;
                while(st[vf]!=*i) sol[nr].push_back(st[vf--]); vf--;
                sol[nr].push_back(nod); sol[nr].push_back(*i);
            }
        }
    }
}
void write ()
{
    cout<<nr<<"\n";
    for(int i=1;i<=nr;i++)
    {
        for(vector <int> :: iterator j=sol[i].begin();j!=sol[i].end();j++)
            cout<<*j<<" ";
        cout<<"\n";
    }
}
int main()
{
    read();
    dfs(1,0);
    write();
    cin.close();
    cout.close();
    return 0;
}