Cod sursa(job #953149)

Utilizator timicsIoana Tamas timics Data 25 mai 2013 04:05:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int N,M,x,y,v[100100],w[100100],low[100100],depth[100100],comp=0;
struct muchie
{
    int nod1;
    int nod2;
};

vector <muchie> m;
vector <vector <int> > c;
vector <int> a[100100];

void dfs(int k, int p, int dep)
{
    v[k]=1;
    depth[k]=dep;
    low[k]=dep;
    int d=a[k].size();

    for(int i=0;i<d;++i)
    {
        if(v[a[k][i]]==0)
        {
            struct muchie z;
            z.nod1=k;
            z.nod2=a[k][i];
            m.push_back(z);

            dfs(a[k][i],k,dep+1);
            low[k]=min(low[k],low[a[k][i]]);
            if(low[a[k][i]]>=depth[k])
            {
                ++comp;
                vector<int> com;
                int t,u,s=m.size();

                do
                {
                    t=m[s-1].nod1;
                    u=m[s-1].nod2;

                    if(w[t]!=comp)
                    {
                        w[t]=comp;
                        com.push_back(t);
                    }

                    if(w[u]!=comp)
                    {
                        w[u]=comp;
                        com.push_back(u);
                    }
                    m.pop_back();
                    --s;
                }
                while(t!=k || u!=a[k][i]);

                c.push_back(com);
            }
        }

        else if(a[k][i]!=p)
            low[k]=min(low[k],depth[a[k][i]]);

    }
    return;
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
    {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for(int i=1;i<=N;++i)
        if(v[i]==0)
            dfs(i,0,0);

    int e=c.size();
    printf("%d\n",comp);
    for(int i=0;i<e;++i)
    {
        int f=c[i].size();
        for(int j=0;j<f;++j)
            printf("%d ",c[i][j]);
        printf("\n");
    }

    return 0;
}