Cod sursa(job #2197040)

Utilizator gapdanPopescu George gapdan Data 20 aprilie 2018 23:45:13
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#define NMAX 100005
 
using namespace std;
 
int n,m,x,y,i,cbc;
int viz[NMAX],lvl[NMAX];
struct punct
{
    int x,y;
};
vector<int>v[NMAX];
set<int>sol[NMAX];
stack<punct>st;
punct per(int a,int b)
{
    punct X;
    X.x=a;X.y=b;
    return X;
 
}
void DFS(int nod,int niv,int tata)
{
    int i;
    viz[nod]=1;
    lvl[nod]=niv;
    for(i=0;i<v[nod].size(); ++i)
    {
        int fiu=v[nod][i];
        if(fiu == tata) continue;
        if(viz[fiu] == 0)
        {
            st.push(per(nod,fiu));
            DFS(fiu,niv+1,nod);
            lvl[nod]=min(lvl[nod],lvl[fiu]);
            if(lvl[fiu] >= niv)
            {
                ++cbc;
                punct X;
                do
                {
                    X=st.top();
                    sol[cbc].insert(X.x);
                    sol[cbc].insert(X.y);
                    st.pop();
                }while(X.x != nod || X.y != fiu);
            }
        }
        else lvl[nod]=min(lvl[nod],lvl[fiu]);
    }
}
int main()
{
    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] == 0) DFS(i,1,0);
    }
    printf("%d\n",cbc);
    for(i=1;i<=cbc;++i)
    {
        set<int>::iterator it;
        for(it=sol[i].begin();it!=sol[i].end();++it) printf("%d ",*it);
        printf("\n");
    }
    return 0;
}