Cod sursa(job #1214472)

Utilizator nicol.bolasNicol Bolas nicol.bolas Data 30 iulie 2014 15:20:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<set>
using namespace std;
#define NMAX 100005
vector <int> v[NMAX];
stack < pair <int,int> > st;
pair <int,int> p;
bitset <NMAX> viz;
set <int> S[NMAX];
set <int>::iterator it;
int n,m,k,x,y,L[NMAX];
void dfs(int nod, int niv, int tata)
{
    int i;
    viz[nod]=1;
    L[nod]=niv;
    for (i=0;i<v[nod].size();++i)
    {
        int fiu=v[nod][i];
        if (fiu==tata)
            continue;
        if (!viz[fiu])
        {
            st.push(make_pair(nod,fiu));
            dfs(fiu,niv+1,nod);
            L[nod]=min(L[fiu],L[nod]);
            if (L[fiu]>=niv)
            {
                ++k;
                do
                {
                    p=st.top(); st.pop();
                    S[k].insert(p.first);
                    S[k].insert(p.second);
                } while (p.first!=nod || p.second!=fiu);
            }
        }
        else
            L[nod]=min(L[fiu],L[nod]);
    }
}
int main()
{
    int i;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (i=1;i<=n;++i)
        if (!viz[i])
            dfs(i,1,0);
    printf("%d\n",k);
    for (i=1;i<=k;++i)
    {
        for (it=S[i].begin();it!=S[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}