Cod sursa(job #951461)

Utilizator marialivia16Chiorean Maria Livia marialivia16 Data 20 mai 2013 17:28:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <iostream>
#include<vector>
#include<stack>
#include<string>
#include<fstream>
#include<algorithm>
#define lim 100001
using namespace std;
class biconex {
    int n,m,sel[lim],t[lim],nr;
    vector<int> v[lim],comp[lim];
    stack<int> stiva;
    fstream in,out;
public:
    biconex(string fin, string fout)
    {
        in.open(fin.c_str(), ios::in);
        out.open(fout.c_str(), ios::out);
        nr=0;
    }
    ~biconex()
    {
        in.close();
        out.close();
    }
    void read()
    {
        int a,b;
        in>>n>>m;
        for(int i=1;i<=m;i++)
        {
            in>>a>>b;
            v[a].push_back(b);
            v[b].push_back(a);

        }
        for(int i=1;i<=n;i++)
        {
            sel[i]=0;
        }

    }
    int dfs(int nod,int niv)
    {
        sel[nod]=niv;
        stiva.push(nod);
        vector<int>::iterator it;
        for(it=v[nod].begin();it<v[nod].end();it++)
        {
            int aux;
            //cout<<*it<<endl;
            if( *it == t[nod] ) continue;
            if(sel[*it]==0)
            {
                stiva.push(nod);
                t[*it]=nod;
                //cout<<"*it: "<<*it<<", niv: "<<niv+1<<endl;
                dfs(*it,niv+1);
                if(sel[*it]>=niv)
                {
                    while(stiva.top()!=nod)
                    {
                        comp[nr].push_back(stiva.top());
                        stiva.pop();
                    }
                    comp[nr].push_back(stiva.top());
                    sort(comp[nr].begin(), comp[nr].end());
                    nr++;
                }
            }
            aux=sel[*it];
            if(sel[nod]>aux)
            {
                sel[nod]=aux;
            }
        }
        return sel[nod];
    }
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            if(sel[i]==0)
            {
                dfs(i,1);
            }
        }
        vector<int>::iterator it;
        out<<nr<<endl;
        for(int i=0;i<nr;i++)
        {
            int sem=0;
            for(it=comp[i].begin();it<comp[i].end();it++)
            {
                sem=0;
                if(*it!=*(it+1))
                {
                    sem=1;
                }
                if(sem==1)
                {
                    out<<*it<<" ";
                }
            }
            out<<endl;
        }
    }
};
int main()
{
    biconex X("biconex.in","biconex.out");
    X.read();
    X.solve();
    return 0;
}