Cod sursa(job #1933071)

Utilizator geo_furduifurdui geo geo_furdui Data 20 martie 2017 13:32:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include<vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> t[100010];
vector <int> sol[100010];
int n,m,st[200010];
int level[100010],nr;
int up[100010],vf;
int used[100010];
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);
    }
}
void dfs (int nod,int dad)
{
    used[nod]=1;
    level[nod]=level[dad]+1;
    up[nod]=level[nod];
    st[++vf]=nod;
    for(vector <int> :: iterator i=t[nod].begin();i!=t[nod].end(); ++i)
    {
        if(used[*i]!=0)
        {
            if(*i!=dad)
                up[nod]=min(up[nod],level[*i]);
        }
            else
            {
                dfs(*i,nod);
                up[nod]=min(up[nod],up[*i]);
                if(up[*i]>=level[nod])
                { ++nr;
                    while(st[vf]!=*i) sol[nr].push_back(st[vf--]);
                    sol[nr].push_back(nod);
                    sol[nr].push_back(*i);
                    --vf;
                }
            }
        }
    }
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;
}