Cod sursa(job #1412650)

Utilizator gapdanPopescu George gapdan Data 1 aprilie 2015 13:33:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<cstdio>
#include<vector>
#include<set>
#include<stack>
#define NMAX 100001
#define min(a,b) (a>b?b:a)
using namespace std;

struct per
{
    int l,r;
};
int n,m,cbc;
int viz[NMAX],low[NMAX];
set<int>s[NMAX];
vector<int>v[NMAX];
stack<per>st;

per pereche(int x,int y)
{
    per X; X.l=x; X.r=y;
    return X;
}

void DFS(int nod,int niv,int tata)
{
    low[nod]=niv;
    viz[nod]=1;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int fiu = v[nod][i];
        if (fiu == tata) continue;
        if (viz[fiu] ==0)
        {
            st.push(pereche(nod,fiu));
            DFS(fiu,niv+1,nod);
            low[nod] = min(low[nod],low[fiu]);
            if (low[fiu] >= niv)
            {
                ++cbc;
                per X;
                do
                {
                    X = st.top();
                    st.pop();
                    s[cbc].insert(X.l);
                    s[cbc].insert(X.r);
                }while(X.l != nod || X.r != fiu);
            }

        }
        else low[nod] = min(low[nod],low[fiu]);
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i)
    {
        if (viz[i] == 0)
        {
            DFS(i,1,0);
        }
    }
    printf("%d\n",cbc);
    for(int i = 1; i <= cbc; ++i)
    {
        set<int>::iterator it;
        for(it = s[i].begin(); it != s[i].end(); ++it)
            printf("%d ",*it);
        printf("\n");
    }

    return 0;
}