Cod sursa(job #2173582)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 15 martie 2018 22:53:45
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
struct aa{int a;int b;int ind;};
vector <aa> v[100002];
set <int> sol[100002];
set <int>::iterator it;
aa muc[100002];
int t[100002],nv[100002],lw[100002],mark[100002],st[100002],nr,nrs;
int egal(aa a,int b,int c)
{
    return (a.a==b&&a.b==c)||(a.a==c&&a.b==b);
}
void dfs(int x)
{
    mark[x]=1;
    lw[x]=nv[x];
    int i,l=v[x].size();
    for(i=0;i<l;i++)
        if(!mark[v[x][i].a])
        {
            t[v[x][i].a]=x;
            nv[v[x][i].a]=nv[x]+1;
            st[++nr]=v[x][i].ind;
            dfs(v[x][i].a);
            if(lw[v[x][i].a]<lw[x])
                lw[x]=lw[v[x][i].a];
            if(lw[v[x][i].a]>=nv[x])
            {
                nrs++;
                while(!egal(muc[st[nr]],x,v[x][i].a))
                {
                    sol[nrs].insert(muc[st[nr]].a);
                    sol[nrs].insert(muc[st[nr]].b);
                    nr--;
                }
                sol[nrs].insert(muc[st[nr]].a);
                sol[nrs].insert(muc[st[nr]].b);
                nr--;
            }
        }
        else
        {
            if(v[x][i].a!=t[x]&&lw[x]>nv[v[x][i].a])
                lw[x]=nv[v[x][i].a];
        }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m,i,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        v[a].push_back({b,b,i});
        v[b].push_back({a,a,i});
        muc[i].a=a;
        muc[i].b=b;
        muc[i].ind=i;
    }
    nv[1]=1;
    dfs(1);
    printf("%d\n",nrs);
    for(i=1;i<=nrs;i++)
    {
        for(it=sol[i].begin();it!=sol[i].end();it++)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}