Cod sursa(job #1929537)

Utilizator geo_furduifurdui geo geo_furdui Data 17 martie 2017 19:15:37
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include<vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int > t[100010],best[100010];
int used[100010];
int n,m,level[100010];
int up[100010],vf;
int st[100010],nrc;
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],up[*i]);}
        else
        {
            dfs(*i,nod);
            up[nod]=min(up[nod],up[*i]);
            if(up[*i]>=level[nod])
            {   ++nrc;
                while(st[vf]!=nod) best[nrc].push_back(st[vf--]);
                best[nrc].push_back(nod);
            }
        }
    }
}
void write ()
{
    cout<<nrc<<"\n";
    for(int i=1;i<=nrc;++i)
    {
        for(vector <int> :: iterator j=best[i].begin();j!=best[i].end(); ++j)
            cout<<*j<<" ";
        cout<<"\n";
    }
}
int main()
{
    read();
    dfs(1,0);
    write();
    cin.close();
    cout.close();
    return 0;
}