Cod sursa(job #1393343)

Utilizator ZenusTudor Costin Razvan Zenus Data 19 martie 2015 12:27:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;

#define NMAX 100007

vector < int > G[NMAX];
vector < vector < int > > tow;
vector < vector < int > > :: iterator it;
vector < int > sol;
stack < pair < int , int > > st;
int low[NMAX] , d[NMAX];
// d[node] = adancimea nodului
// low[node] = nivelul minim cu maxim o latura de intoarcere din subarborele lui
int N,M,i,j,x,y;

void df(int node,int father)
{
    vector < int > :: iterator it;

    d[node] = low[node] = d[father] + 1;

    for (it=G[node].begin();it!=G[node].end();++it)
    {
        int c = *it;

        if (c != father && d[c]<d[node])
        st.push(make_pair(node,c));

        if (d[c] == -1) // nu a fost vizitat
        {
            df(c,node);

            low[node] = min(low[node] , low[c]);

            if (d[node] <= low[c])
            {
                if (st.top() == make_pair(node , c))
                sol.push_back(c);

                sol.push_back(st.top().first);

                while (st.top() != make_pair(node,c))
                {
                    st.pop();
                    sol.push_back(st.top().first);
                }

                st.pop();
                sort(sol.begin(),sol.end());
                sol.resize(distance(sol.begin(),unique(sol.begin(),sol.end())));
                tow.push_back(sol);
                sol.clear();
            }
        }
        else if (c != father)
        low[node] = min (low[node] , d[c]);
    }
}

int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");

f>>N>>M;

for (i=1;i<=M;++i)
{
    f>>x>>y;

    G[x].push_back(y);
    G[y].push_back(x);
}

for (i=1;i<=N;++i)
d[i] = -1;

df(1,0);

g<<tow.size()<<'\n';
for (it=tow.begin();it!=tow.end();++it)
{
    sol = *it;

    for (j=0;j<sol.size();++j)
    g<<sol[j]<<" ";

    g<<'\n';
}

return 0;
}