Cod sursa(job #1022480)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 5 noiembrie 2013 15:45:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 100000+5
#define MMAX 200000+5
using namespace std;
int N,M,cbc;
int T[NMAX];
int DFNr[NMAX];
int Cnt[NMAX];
vector<int> CBC[NMAX];
vector<int> V[NMAX];
vector<pair<int,int> > E;
void add(int x,int y)
{
    cbc++;
    while(!(x==E.back().first && y==E.back().second))
    {
        CBC[cbc].push_back(E.back().first);
        CBC[cbc].push_back(E.back().second);
        E.pop_back();
    }
    CBC[cbc].push_back(E.back().first);
    CBC[cbc].push_back(E.back().second);
    E.pop_back();
}
void DFS(int nod)
{
    vector<int>::iterator it;
    for(it=V[nod].begin();it!=V[nod].end();it++)
        if(DFNr[*it]==0)
        {
            E.push_back(make_pair(nod,*it));
            DFNr[*it]=Cnt[*it]=DFNr[nod]+1;
            T[*it]=nod;
            DFS(*it);
            Cnt[nod]=min(Cnt[nod],Cnt[*it]);
            if(Cnt[*it]>=DFNr[nod]) add(nod,*it);
        }
        else
        {
            if(T[nod]!=*it) Cnt[nod]=min(Cnt[nod],DFNr[*it]);
        }
}
int main()
{
    int i,a,b;
    vector<int>::iterator it;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        V[a].push_back(b);
        V[b].push_back(a);
    }
    DFNr[1]=1;
    DFS(1);
    printf("%d\n",cbc);
    for(i=1;i<=cbc;i++)
    {
        sort(CBC[i].begin(),CBC[i].end());
        printf("%d ",CBC[i].front());
        for(it=CBC[i].begin()+1;it!=CBC[i].end();it++)
            if(*it!=*(it-1)) printf("%d ",*it);
        printf("\n");
    }
    return 0;
}